Adjacent Increasing Subarrays Detection I

main.md

Question

Approach

I note a subarray of length k is strictly increasing iff each adjacent pair inside it is increasing, i.e. there are k-1 positions i..i+k-2 where nums[t] < nums[t+1]. So I build a binary array incpair where incpair[i] = 1 iff nums[i] < nums[i+1]. Then I build a prefix sum over incpair so I can test in O(1) whether any length-k window has k-1 increasing pairs. Finally I scan a from 0 to n - 2*k and check whether both windows starting at a and a+k are strictly increasing.

Implementation

class Solution:
    def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if 2 * k > n:
            return False

        incpair = [1 if nums[i] < nums[i+1] else 0 for i in range(n-1)]
        pref = [0] * (n)
        for i in range(n-1):
            pref[i+1] = pref[i] + incpair[i]

        need = k - 1
        for a in range(0, n - 2*k + 1):
            first_count = pref[a + k - 1] - pref[a]
            if first_count != need:
                continue
            second_count = pref[a + 2*k - 1] - pref[a + k]
            if second_count == need:
                return True
        return False

Complexities

• Time: O(n)
• Space: O(n)

🤯