Leetcode Daily - Adjacent Increasing Subarrays Detection I

Here is two solution for problem “Adjacent Increasing Subarrays Detection I”

1. Input, Output, Constraints

  1. Input:
  • nums: an array of integers

  • k: an integer, length of each subarray

  1. Output:
  • True if there exist two adjacent subarrays of length k that are both strictly increasing

  • Otherwise, False

  1. 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