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:
nums[a..a + k - 1] and nums[b..b + k - 1] are strictly increasing.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:
2 is [7, 8, 9], which is strictly increasing.5 is [2, 3, 4], which is also strictly increasing.true.Example 2:
Input: nums = [1,2,3,4,4,4,4,5,6,7], k = 5
Output: false
Constraints:
2 <= nums.length <= 1001 < 2 * k <= nums.length-1000 <= nums[i] <= 1000Problem Overview: You are given an integer array and a value k. The task is to determine whether the array contains two adjacent strictly increasing subarrays, each of length k. In other words, check if there exists an index i where nums[i..i+k-1] and nums[i+k..i+2k-1] are both strictly increasing sequences.
Approach 1: Two Pointers for Check (O(n) time, O(1) space)
This method scans the array and measures the length of strictly increasing segments using two pointers. Start from the left and expand the right pointer while nums[r] > nums[r-1]. This gives the length of a continuous increasing run. If a run length is at least 2k, or if two consecutive runs each have length at least k, you can form two adjacent increasing subarrays. The algorithm only tracks boundaries and lengths, so no extra data structures are required.
The key insight: strictly increasing subarrays must lie inside increasing runs. Instead of checking every possible pair explicitly, compute run lengths and verify whether the required adjacent segments exist.
Approach 2: Sliding Window Technique (O(n) time, O(1) space)
The sliding window approach checks windows of size k while maintaining whether each window is strictly increasing. Move a window across the array and track violations where nums[i] <= nums[i-1]. Two consecutive windows are valid if both satisfy the increasing condition and the second starts exactly after the first.
To optimize, maintain a running count of increasing comparisons inside the window. As the window slides forward, update the count instead of recomputing the entire window. This converts a naive O(nk) check into an O(n) scan while keeping constant space.
This technique is a common pattern in sliding window problems where local order constraints must be verified efficiently.
Recommended for interviews: The two‑pointer run-length scan is typically what interviewers expect. It directly models how increasing sequences behave and produces a clean O(n) solution with constant memory. A sliding window implementation also works and demonstrates familiarity with two pointers and window maintenance patterns. Showing the brute reasoning first (checking segments) and then optimizing to a single pass highlights strong problem-solving skills.
This approach uses a single loop and checks both subarrays simultaneously to see if they are strictly increasing. By maintaining two pointers, one for the first subarray and one for the potential adjacent subarray, we can efficiently determine if there exists any pair of strictly increasing adjacent subarrays.
This function first checks if a subarray starting at the given index with length k is strictly increasing. The main function iterates through the array with initial index such a way that enough elements remain for two subarrays of length k. If at any such index both subarrays are strictly increasing, it returns true.
Time Complexity: O(n * k), where n is the length of the array. The two pointer approach still checks each element of both subarrays.
Space Complexity: O(1), as no additional space is used apart from a few counters.
The sliding window technique can provide a more efficient approach by iterating through the array once and maintaining running comparisons. Continuously evaluate if the latest element extends an increasing pattern and reset boundaries where necessary.
The solution uses a counter that increments through every consecutive pair increase. Two adjacent subarrays need k-1 increases each plus the adjacent element, hence k*2-1 successful increments confirm the presence of two such subarrays.
Time Complexity: O(n)
Space Complexity: O(1)
According to the problem description, we only need to find the maximum length of adjacent increasing subarrays mx. If mx \ge k, then there exist two adjacent strictly increasing subarrays of length k.
We can use a single pass to calculate mx. Specifically, we maintain three variables: cur and pre represent the length of the current increasing subarray and the previous increasing subarray respectively, while mx represents the maximum length of adjacent increasing subarrays.
Whenever we encounter a non-increasing position, we update mx, assign cur to pre, and reset cur to 0. The update formula for mx is mx = max(mx, \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 check whether mx is greater than or equal to k.
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 |
|---|---|
| Using Two Pointers for Check | Time Complexity: O(n * k), where n is the length of the array. The two pointer approach still checks each element of both subarrays. |
| Using Sliding Window Technique | Time Complexity: O(n) |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers (Run Length Scan) | O(n) | O(1) | Best general solution. Efficient single pass when checking increasing runs. |
| Sliding Window Technique | O(n) | O(1) | Useful when explicitly validating fixed-size windows or practicing window-based patterns. |
Adjacent Increasing Subarrays Detection I | Simple and Intuitive | Leetcode 3349 | codestorywithMIK • codestorywithMIK • 7,939 views views
Watch 9 more video solutions →Practice Adjacent Increasing Subarrays Detection I with our built-in code editor and test cases.
Practice on FleetCode