Adjacent Increasing Subarrays Detection II

main.md

Question

Approach

I first compute lenInc[i] = the length of the longest strictly-increasing subarray starting at index i (so lenInc[i] >= 1). A subarray of length k starting at i is strictly increasing iff lenInc[i] >= k. Given that, two adjacent strictly increasing subarrays of length k starting at a and a+k exist iff there is an index a with lenInc[a] >= k and lenInc[a+k] >= k.

Implementation

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        lenInc = [1] * n
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                lenInc[i] = lenInc[i + 1] + 1
            else:
                lenInc[i] = 1

        def can(k: int) -> bool:
            limit = n - 2 * k
            if limit < 0:
                return False
            for a in range(0, limit + 1):
                if lenInc[a] >= k and lenInc[a + k] >= k:
                    return True
            return False

        lo, hi = 1, n // 2
        ans = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if can(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

Complexities

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