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:
nums[a..a + k - 1] and nums[b..b + k - 1] are strictly increasing.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:
[7, 8, 9], which is strictly increasing.[2, 3, 4], which is also strictly increasing.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:
[1, 2], which is strictly increasing.[3, 4], which is also strictly increasing.k for which two such adjacent strictly increasing subarrays exist.
Constraints:
2 <= nums.length <= 2 * 105-109 <= nums[i] <= 109Problem Overview: You are given an integer array. The task is to find the largest k such that two adjacent subarrays of length k are both strictly increasing. The first subarray must end exactly where the second begins, so the ranges look like [i-k+1 ... i] and [i+1 ... i+k].
Approach 1: Dynamic Programming (O(n) time, O(n) space)
Track how long the increasing sequence is at every index. Create two arrays: incEnd[i] (length of the strictly increasing subarray ending at i) and incStart[i] (length of the strictly increasing subarray starting at i). Compute incEnd in a left‑to‑right pass and incStart in a right‑to‑left pass. For every boundary i, the largest valid k using that boundary is min(incEnd[i], incStart[i+1]). Scan all boundaries and keep the maximum. This approach is easy to reason about and clearly separates the two subarrays. Time complexity is O(n) and space complexity is O(n). The technique is a classic pattern when working with monotonic segments in array problems.
Approach 2: Optimized Single Pass (O(n) time, O(1) space)
Instead of storing DP arrays, observe that strictly increasing portions form contiguous runs. Suppose one run has length L. Inside the same run you can place both adjacent subarrays if 2k ≤ L, giving k = L / 2. If two runs of lengths L and R meet at a decreasing boundary, the first subarray can end in the left run and the second can start in the right run, giving k = min(L, R). Iterate once through the array, compute each increasing run length, and update the answer using these two cases. This eliminates the DP arrays while keeping the same O(n) time complexity and reducing space to O(1). Problems involving monotonic runs often appear alongside techniques like binary search or two‑pointer scans in competitive programming.
Recommended for interviews: Start with the DP explanation because it shows you understand how to measure increasing segments from both directions. Then move to the single‑pass run‑length optimization. Interviewers usually expect the O(n) time and O(1) space approach because it demonstrates pattern recognition with increasing runs in array traversal.
The idea is to use a dynamic programming technique that calculates the length of the longest increasing subarray that ends at each position.
We maintain an array inc[], where inc[i] stores the length of the longest strictly increasing subarray ending at index i.
Once this array is filled, the solution is to find two adjacent values in inc[] where both values are at least k. Because they are adjacent, they indicate two subarrays of length k each, which are strictly increasing.
The C solution uses an array inc to track the length of increasing subarrays. It iterates through the input array, updating inc to hold the length of the current increasing sequence ending at each position. Finally, it looks for two adjacent lengths in inc that are both larger than max_k.
Time Complexity: O(n) due to a single pass through the array to fill the inc array.
Space Complexity: O(n) due to the inc array.
This method optimizes the space usage by relying on two variables instead of an entire array. The goal is to calculate the length of current increasing sequences directly within the loop.
We keep two lengths, current and previous, to track increasing subarrays as we iterate through the input array.
The C solution uses two variables instead of an array to track the lengths of the current and previous increasing subarrays, reducing the space complexity.
Time Complexity: O(n).
Space Complexity: O(1).
We can use a single pass to calculate the maximum length of adjacent increasing subarrays ans. Specifically, we maintain three variables: cur and pre represent the length of the current increasing subarray and the previous increasing subarray respectively, while ans represents the maximum length of adjacent increasing subarrays.
Whenever we encounter a non-increasing position, we update ans, assign cur to pre, and reset cur to 0. The update formula for ans is ans = max(ans, \lfloor \frac{cur}{2} \rfloor, min(pre, cur)), meaning the adjacent increasing subarrays come from either half the length of the current increasing subarray, or the smaller value between the previous increasing subarray and the current increasing subarray.
Finally, we just need to return ans.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n) due to a single pass through the array to fill the |
| Approach 2: Optimized Single Pass | Time Complexity: O(n). |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (prefix & suffix increasing lengths) | O(n) | O(n) | Best for clarity. Easy to reason about boundaries between two adjacent subarrays. |
| Optimized Single Pass (run-length tracking) | O(n) | O(1) | Preferred in interviews and large inputs where constant space matters. |
Adjacent Increasing Subarrays Detection II | Same as Part I | Leetcode 3350 | codestorywithMIK • codestorywithMIK • 6,933 views views
Watch 9 more video solutions →Practice Adjacent Increasing Subarrays Detection II with our built-in code editor and test cases.
Practice on FleetCode