Skip to main content
Talentd

Adjacent Increasing Subarrays Detection II - Solution & Explanation

MediumArrayBinary Search20 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Approach 1: Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Optimized Single Pass

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Single Pass

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Dynamic Programming

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.

Approach 2: Optimized Single Pass

Time Complexity: O(n).
Space Complexity: O(1).

Single Pass—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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.

Video Solution

Adjacent Increasing Subarrays Detection II | Same as Part I | Leetcode 3350 | codestorywithMIK • codestorywithMIK • 7,053 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Adjacent Increasing Subarrays Detection II easy or hard?
Adjacent Increasing Subarrays Detection II is generally considered a Medium difficulty problem. The challenge is recognizing that strictly increasing segments form runs and that the answer can be derived from run lengths rather than checking every possible subarray.
Adjacent Increasing Subarrays Detection II Python/Java solution
Python and Java implementations usually compute increasing run lengths while iterating through the array. The optimized solution maintains current run length and previous run length, updating the maximum possible k during the scan. Both implementations run in O(n) time.
How to solve Adjacent Increasing Subarrays Detection II in O(n)?
Traverse the array and measure lengths of strictly increasing segments. For each segment of length L, you can place two adjacent increasing subarrays inside it with k = L / 2. For two consecutive segments with lengths L and R, you can place them across the boundary with k = min(L, R). Track the maximum k while scanning.
What is the best approach for Adjacent Increasing Subarrays Detection II?
The best approach is a single-pass run-length method. Treat the array as a series of strictly increasing runs and compute the maximum k using two cases: placing both subarrays inside one run (k = runLength / 2) or across two consecutive runs (k = min(leftRun, rightRun)). This runs in O(n) time and O(1) space.
Is Adjacent Increasing Subarrays Detection II asked at Google/Amazon/Meta?
Problems involving increasing runs and subarray boundaries frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem ID may vary, recognizing increasing segments and optimizing to O(n) is a common interview pattern.
What data structure is used in Adjacent Increasing Subarrays Detection II?
The problem mainly uses array traversal and run-length tracking. A dynamic programming variant uses two arrays to store increasing lengths from the left and right, while the optimized solution only keeps integer counters.
What is the time complexity of Adjacent Increasing Subarrays Detection II?
The optimal solution runs in O(n) time because the array is scanned once while tracking lengths of increasing runs. A DP version using prefix and suffix arrays also runs in O(n) time but uses O(n) additional space.

Ready to solve this problem?

Practice Adjacent Increasing Subarrays Detection II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays