Adjacent Increasing Subarrays Detection I

Difficulty: Easy | Acceptance: 48.00% | Paid: No Topics: Array

Given an array nums and an integer k, return true if there are two adjacent subarrays of length k that are strictly increasing, or false otherwise. A subarray nums[i…j] is strictly increasing if nums[l] < nums[l+1] for all l in the range [i, j-1].

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Precompute Increasing Runs

Examples

Example 1

Input:

nums = [2,5,7,8,9,2,3,4,3,1], k = 3

Output:

true

Explanation: The subarray starting at index 2 is [7, 8, 9], which is strictly increasing.

The subarray starting at index 5 is [2, 3, 4], which is also strictly increasing.

These two subarrays are adjacent, so the result is true.

Example 2

Input:

nums = [1,2,3,4,4,4,4,5,6,7], k = 5

Output:

false

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= nums.length / 2

Approach 1: Brute Force

Intuition Iterate through all possible starting positions for the first subarray and check if both the first and the adjacent second subarray are strictly increasing.

Steps

• Iterate through the array from index 0 to n - 2*k.
• For each starting index i, check if the subarray nums[i…i+k-1] is strictly increasing.
• If the first subarray is valid, check if the adjacent subarray nums[i+k…i+2*k-1] is strictly increasing.
• If both are valid, return true.
• If the loop finishes without finding such a pair, return false.

from typing import List

class Solution:
    def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for i in range(n - 2 * k + 1):
            valid = True
            for j in range(i, i + k - 1):
                if nums[j] >= nums[j + 1]:
                    valid = False
                    break
            if not valid:
                continue
            for j in range(i + k, i + 2 * k - 1):
                if nums[j] >= nums[j + 1]:
                    valid = False
                    break
            if valid:
                return True
        return False

Complexity

• Time: O(n * k)
• Space: O(1)
• Notes: Simple to implement but can be slow for large inputs.

Approach 2: Precompute Increasing Runs

Intuition Precompute the length of the strictly increasing run ending at each index. Then, check if there exists an index where the run length is at least k and the run length k indices ahead is also at least k.

Steps

• Create an array inc where inc[i] stores the length of the strictly increasing subarray ending at index i.
• Iterate through nums to fill inc. If nums[i] > nums[i-1], then inc[i] = inc[i-1] + 1, otherwise inc[i] = 1.
• Iterate through inc from index k-1 to n-k-1.
• For each index i, check if inc[i] >= k and inc[i+k] >= k.
• If both conditions are met, return true.
• If the loop finishes, return false.

from typing import List

class Solution:
    def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        inc = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                inc[i] = inc[i - 1] + 1
            else:
                inc[i] = 1
        
        for i in range(k - 1, n - k):
            if inc[i] >= k and inc[i + k] >= k:
                return True
        return False

Complexity

• Time: O(n)
• Space: O(n)
• Notes: More efficient time complexity compared to brute force, using extra space to store run lengths.