Leetcode Daily - Adjacent Increasing Subarrays Detection I
Here is two solution for problem “Adjacent Increasing Subarrays Detection I”
1. Input, Output, Constraints
- Input:
-
nums: an array of integers
-
k: an integer, length of each subarray
- Output:
-
True if there exist two adjacent subarrays of length k that are both strictly increasing
-
Otherwise, False
- Constraints:
-
2 ≤ k ≤ len(nums) ≤ 10⁵
-
-10⁹ ≤ nums[i] ≤ 10⁹
-
Example:
Input: nums = [2,5,7,8,9,2,3,4,3,1], k = 3
Output: True
Explanation:
[7,8,9] (start index 2) and [2,3,4] (start index 5)
are both strictly increasing and adjacent.
2. Dry Run Ideas
We look for two increasing subarrays of length k, whose start indices differ by k.
Example walkthrough:
Start index Subarray Increasing?
0 [2,5,7] ✅
1 [5,7,8] ✅
2 [7,8,9] ✅
3 [8,9,2] ❌
4 [9,2,3] ❌
5 [2,3,4] ✅
Two valid ones:
[7,8,9] at index 2
[2,3,4] at index 5 → difference = 3 = k ✅
→ Output = True
3. Solution 1: O(N·k) — Simple Sliding Window
Brute-force check all windows and their adjacent pair.
def hasAdjacentIncreasingSubarrays(nums, k):
n = len(nums)
def is_increasing(start):
for i in range(start, start + k - 1):
if nums[i] >= nums[i + 1]:
return False
return True
for i in range(n - 2 * k + 1):
if is_increasing(i) and is_increasing(i + k):
return True
return False
-
Time: O(N * k)
-
Space: O(1)
4. Solution 2: O(N) — Precompute Increasing Streaks
-
Idea:
- Build an array inc[i] = length of increasing sequence starting at index i.
- If both inc[i] ≥ k and inc[i + k] ≥ k, we found two adjacent increasing subarrays.
-
Example trace:
nums = [2,5,7,8,9,2,3,4,3,1]
→ inc = [5,4,3,2,1,3,2,1,1,1]
- At i = 2: inc[2] = 3, inc[5] = 3 → ✅
Code:
def hasAdjacentIncreasingSubarrays(nums, k):
n = len(nums)
inc = [1] * n
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
inc[i] = inc[i + 1] + 1
for i in range(n - 2 * k + 1):
if inc[i] >= k and inc[i + k] >= k:
return True
return False
✅ Correctness: Uses precomputed increasing streaks
Complexity:
-
Time: O(N)
-
Space: O(N)
Last Updated On October 14, 2025