3349. Adjacent Increasing Subarrays Detection 1

Problem Statement in English

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

Return true if there exist two adjacent, non-overlapping, and strictly increasing subarrays of length k in nums, and false otherwise.

Approach

We simply find all the starting indices of increasing subarrays of length k and store them in a set.

Then we check if there are two indices in the set such that they differ by k.

Solution in Python

class Solution:
    def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
        s = set()
        q = deque()

        for i in range(len(nums)):
            if q and nums[q[-1]] >= nums[i]:
                q = deque([i])
            else:
                q.append(i)

                if len(q) == k:
                    s.add(q.popleft())

        s = set(sorted(s))

        for n in s:
            if n + k in s:
                return True

        return False

Complexity

• Time: $O(n \log n)$
  Since we employ a sort. We could skip that and just use a hash set, which would make it $O(n)$. But for some reason this was faster on leetcode.

• Space: $O(n)$
  Since we are using a set and a deque.

And we are done.