Problem Statement in English

You’re given a 0-indexed integer array nums.

Return the maximum length of two adjacent, non-overlapping, and strictly increasing subarrays in nums.

Approach

The idea is that we first find the starting index of every increasing subarray and store them.

From here there can be 2 cases:

  • either one of the individual subarrays we found has 2*k length, in which case we can take the first k elements as one subarray and the last k elements as the other subarray, thus giving us a length of k.

  • the other case is that two adjacent increasing subarrays are formed by two adjacent increasing subarrays we found. In this case, the length of the two subarrays will be limited by the smaller of the two subarrays.

And that’s it.

Solution in Python


class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        arr = []
        res = 1
        ln = len(nums)

        l = 0
        for r in range(1, ln):
            if nums[r - 1] >= nums[r]:
                res = max(res, (r - l) // 2)

                arr.append((l, r))
                l = r

        if l != ln - 1:
            r = ln

            res = max(res, (r - l) // 2)
            arr.append((l, r))

        for i in range(1, len(arr)):
            p1 = arr[i - 1]
            p2 = arr[i]

            if p1[1] == p2[0]:
                res = max(res, min(p1[1] - p1[0], p2[1] - p2[0]))

        return res

Complexity

  • Time: $O(n)$
    Since we iterate over the array once.

  • Space: $O(n)$
    Since we store indices of increasing subarrays.

And we are done.