We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Adjacent Increasing Subarrays Detection I

Number: 3612

Difficulty: Easy

Paid? No

Companies: Google, Amazon

Problem Description

Given an integer array nums and an integer k, determine if there exist two adjacent subarrays of length k that are both strictly increasing. That is, find an index a such that the subarray starting at a and the next subarray starting at a+k are both strictly increasing.

Key Insights

  • The two subarrays must be contiguous in nums; the second starts exactly after the first ends.
  • A strictly increasing subarray means every element is less than the subsequent element.
  • Iterate over all valid starting positions for the first subarray (from index 0 to index n - 2*k) and check both subarrays.
  • Since the input size is small (n up to 100), an O(n*k) solution is acceptable.

Space and Time Complexity

Time Complexity: O(n*k) where n is the length of nums and k is the subarray length. Space Complexity: O(1) as we use a constant amount of extra space.

Solution

We use a sliding window approach to check every possible pair of adjacent subarrays of length k. For each starting index a (from 0 to n - 2k), we verify if nums[a..a+k-1] and nums[a+k..a+2k-1] are strictly increasing. A helper function can be utilized to check if a given subarray is strictly increasing by iterating through its elements and confirming that each element is less than the next one.

Code Solutions

def is_strictly_increasing(sub):
    # Check if each element is less than the next element in the subarray
    for i in range(len(sub) - 1):
        if sub[i] >= sub[i+1]:
            return False
    return True

def adjacentIncreasingSubarrays(nums, k):
    n = len(nums)
    # Iterate over all possible starting indices for the first subarray
    for start in range(0, n - 2 * k + 1):
        first_sub = nums[start:start+k]
        second_sub = nums[start+k:start+2*k]
        # Check if both subarrays are strictly increasing
        if is_strictly_increasing(first_sub) and is_strictly_increasing(second_sub):
            return True  # Found two adjacent increasing subarrays
    return False  # No valid pair was found

# Example usage:
print(adjacentIncreasingSubarrays([2,5,7,8,9,2,3,4,3,1], 3))  # True
← Back to All Questions