Scale Engineer

Adjacent Increasing Subarrays Detection II

Med
#2976Time: O(n^3). The outer loop for `k` runs up to `n/2` times. The middle loop for `a` runs up to `n` times. The check for each pair of subarrays takes `O(k)` time. In the worst case, this is `O(n * n * n)`.Space: O(1) extra space, as we are not using any auxiliary data structures that scale with the input size.
Algorithms
Binary Search
Data structures
Array

Prompt

Given an array nums of n integers, your task is to find the maximum value of k for which there exist two adjacent subarrays of length k each, such that both subarrays are strictly increasing. Specifically, check if there are two subarrays of length k 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 the maximum possible value of k.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

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

Output: 3

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, and 3 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

Example 2:

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

Output: 2

Explanation:

  • The subarray starting at index 0 is [1, 2], which is strictly increasing.
  • The subarray starting at index 2 is [3, 4], which is also strictly increasing.
  • These two subarrays are adjacent, and 2 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

 

Constraints:

  • 2 <= nums.length <= 2 * 105
  • -109 <= nums[i] <= 109

Approaches

4 approaches with complexity analysis and trade-offs.

This approach involves checking every possible length k and every possible starting position a. For each combination, it verifies if the two adjacent subarrays of length k are strictly increasing.

Algorithm

  1. Iterate through all possible lengths k from n/2 down to 1. The first k that satisfies the condition will be the maximum, so we can return it immediately.
  2. For each k, iterate through all possible starting indices a for the first subarray, from 0 to n - 2k.
  3. For each pair (k, a), define two subarrays: sub1 = nums[a...a+k-1] and sub2 = nums[a+k...a+2k-1].
  4. Use a helper function isIncreasing(subarray) that checks if a given subarray is strictly increasing. This function iterates through the subarray and checks if sub[i] > sub[i-1] for all i.
  5. If both sub1 and sub2 are strictly increasing, we have found our maximum k and can return it.
  6. If the loops complete without finding a valid k, it means no such pair of subarrays exists, so we return 0.

Walkthrough

The most straightforward method is to test every possibility. We can iterate through all potential lengths k, starting from the largest possible (n/2) down to 1. For each k, we check every possible starting position a. At each position, we form two adjacent subarrays of length k and check if both are strictly increasing. The first value of k for which we find such a pair of subarrays is the maximum possible k.

class Solution {    private boolean isIncreasing(int[] nums, int start, int end) {        for (int i = start + 1; i <= end; i++) {            if (nums[i] <= nums[i - 1]) {                return false;            }        }        return true;    }     public int findMaximumK(int[] nums) {        int n = nums.length;        for (int k = n / 2; k >= 1; k--) {            for (int a = 0; a <= n - 2 * k; a++) {                // Check first subarray: nums[a...a+k-1]                boolean firstOk = isIncreasing(nums, a, a + k - 1);                // Check second subarray: nums[a+k...a+2k-1]                boolean secondOk = isIncreasing(nums, a + k, a + 2 * k - 1);                 if (firstOk && secondOk) {                    return k; // Found the largest k, return immediately                }            }        }        return 0;    }}

Complexity

Time

O(n^3). The outer loop for `k` runs up to `n/2` times. The middle loop for `a` runs up to `n` times. The check for each pair of subarrays takes `O(k)` time. In the worst case, this is `O(n * n * n)`.

Space

O(1) extra space, as we are not using any auxiliary data structures that scale with the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • Extremely inefficient and will result in a 'Time Limit Exceeded' error for large inputs.

Solutions

class Solution {public  int maxIncreasingSubarrays(List<Integer> nums) {    int ans = 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)) {        ans = Math.max(ans, Math.max(cur / 2, Math.min(pre, cur)));        pre = cur;        cur = 0;      }    }    return ans;  }}

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