Scale Engineer

Adjacent Increasing Subarrays Detection I

Easy
#2975Time: O(n * k). The outer loop runs `n - 2k + 1` times, which is `O(n)`. Inside the loop, we call `isIncreasing` twice. Each call takes `O(k)` time. Thus, the total time complexity is `O(n * k)`.Space: O(1). We only use a few variables for loops and indices, which does not depend on the input size.
Data structures
Array

Prompt

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.

 

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:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. We iterate through all possible starting positions for the first of the two adjacent subarrays. For each position, we check if the two corresponding subarrays of length k are strictly increasing.

Algorithm

  • Define a helper function isIncreasing(nums, start, k):
    • Loop i from start to start + k - 2.
    • If nums[i] >= nums[i+1], return false.
    • After the loop, return true.
  • In the main function, get the length of the array, n.
  • Loop a from 0 to n - 2*k.
  • Check if isIncreasing(nums, a, k) is true.
  • Check if isIncreasing(nums, a + k, k) is true.
  • If both are true, return true.
  • If the loop completes, return false.

Walkthrough

We can write a helper function, isIncreasing(nums, start, k), that checks if the subarray of length k starting at start is strictly increasing. This function iterates from start to start + k - 2, comparing nums[i] with nums[i+1]. If it finds any pair where nums[i] >= nums[i+1], it returns false. If the loop completes, it returns true.

The main function will loop through all possible starting indices a for the first subarray. The loop for a will run from 0 to n - 2k, where n is the length of nums. This range ensures that two full subarrays of length k fit within the array bounds.

Inside the loop, for each a, we call isIncreasing(nums, a, k) to check the first subarray and isIncreasing(nums, a + k, k) to check the second, adjacent subarray.

If both calls return true, we have found our pair, and we can immediately return true.

If the loop finishes without finding such a pair, it means none exist, so we return false.

class Solution {    private boolean isIncreasing(int[] nums, int start, int k) {        for (int i = start; i < start + k - 1; i++) {            if (nums[i] >= nums[i + 1]) {                return false;            }        }        return true;    }     public boolean solve(int[] nums, int k) {        int n = nums.length;        if (2 * k > n) {            return false;        }        for (int a = 0; a <= n - 2 * k; a++) {            boolean firstSubarrayIsIncreasing = isIncreasing(nums, a, k);            boolean secondSubarrayIsIncreasing = isIncreasing(nums, a + k, k);            if (firstSubarrayIsIncreasing && secondSubarrayIsIncreasing) {                return true;            }        }        return false;    }}

Complexity

Time

O(n * k). The outer loop runs `n - 2k + 1` times, which is `O(n)`. Inside the loop, we call `isIncreasing` twice. Each call takes `O(k)` time. Thus, the total time complexity is `O(n * k)`.

Space

O(1). We only use a few variables for loops and indices, which does not depend on the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Low memory usage.

Cons

  • Can be inefficient for large n and k, as it performs redundant comparisons for overlapping parts of subarrays in consecutive iterations.

Solutions

class Solution {public  boolean hasIncreasingSubarrays(List<Integer> nums, int k) {    int mx = 0, pre = 0, cur = 0;    int n = nums.size();    for (int i = 0; i < n; ++i) {      ++cur;      if (i == n - 1 || nums.get(i) >= nums.get(i + 1)) {        mx = Math.max(mx, Math.max(cur / 2, Math.min(pre, cur)));        pre = cur;        cur = 0;      }    }    return mx >= k;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem