Watch 10 video solutions for Adjacent Increasing Subarrays Detection II, a medium level problem involving Array, Binary Search. This walkthrough by codestorywithMIK has 6,933 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |