Problem

Given an array nums of n integers and an integer k, determine whether there exist two adjacent subarrays of length k such that both subarrays are strictly increasing. Specifically, check if there are two subarrays starting at indices a and b (a < b), where:

  • Both subarrays nums[a..a + k - 1] and nums[b..b + k - 1] are strictly increasing.
  • The subarrays must be adjacent, meaning b = a + k.

Return true if it is possible to find two such subarrays, and false otherwise.

Examples

Example 1:

1
2
3
4
5
6
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:

1
2
Input: nums = [1,2,3,4,4,4,4,5,6,7], k = 5
Output: false

Constraints:

  • 2 <= nums.length <= 100
  • 1 < 2 * k <= nums.length
  • -1000 <= nums[i] <= 1000

Solution

Method 1 – Sliding Window Check

Intuition

We need to find two adjacent subarrays of length k that are both strictly increasing. By sliding a window of size 2k across the array, we can check if both halves of the window (each of length k) are strictly increasing. If so, return true.

Approach

  1. Iterate over all possible starting indices i for the first subarray, from 0 to len(nums) - 2*k + 1.
  2. For each i, check if the subarray nums[i:i+k] is strictly increasing.
  3. Also check if the next subarray nums[i+k:i+2*k] is strictly increasing.
  4. If both are strictly increasing, return true.
  5. If no such pair is found, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
  bool areTwoAdjacentIncreasingSubarrays(vector<int>& nums, int k) {
    int n = nums.size();
    for (int i = 0; i <= n - 2 * k; ++i) {
      bool first = true, second = true;
      for (int j = i; j < i + k - 1; ++j) {
        if (nums[j] >= nums[j + 1]) {
          first = false;
          break;
        }
      }
      if (!first) continue;
      for (int j = i + k; j < i + 2 * k - 1; ++j) {
        if (nums[j] >= nums[j + 1]) {
          second = false;
          break;
        }
      }
      if (second) return true;
    }
    return false;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public boolean areTwoAdjacentIncreasingSubarrays(int[] nums, int k) {
    int n = nums.length;
    for (int i = 0; i <= n - 2 * k; i++) {
      boolean first = true, second = true;
      for (int j = i; j < i + k - 1; j++) {
        if (nums[j] >= nums[j + 1]) {
          first = false;
          break;
        }
      }
      if (!first) continue;
      for (int j = i + k; j < i + 2 * k - 1; j++) {
        if (nums[j] >= nums[j + 1]) {
          second = false;
          break;
        }
      }
      if (second) return true;
    }
    return false;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def areTwoAdjacentIncreasingSubarrays(self, nums: list[int], k: int) -> bool:
    n = len(nums)
    for i in range(n - 2 * k + 1):
      first = all(nums[j] < nums[j + 1] for j in range(i, i + k - 1))
      if not first:
        continue
      second = all(nums[j] < nums[j + 1] for j in range(i + k, i + 2 * k - 1))
      if second:
        return True
    return False

Complexity

  • ⏰ Time complexity: O(n * k) (where n is the length of nums)
  • 🧺 Space complexity: O(1)