Adjacent Increasing Subarrays Detection II solution and explanation
Google
9 more videos on this problem
Adjacent Increasing Subarrays Detection II | Same as Part I | Leetcode 3350 | codestorywithMIKcodestorywithMIK · 15:51 · 7K views
3349 & 3350. Adjacent Increasing Subarrays Detection I & II | Binary Search | DPAryan Mittal · 16:00 · 3K views
3350. Adjacent Increasing Subarrays Detection II | Leetcode Daily - PythonLeetcode Daily · 6:50 · 838 views
Daily Leetcode #2024: Oct 15, 2025 - 3350. Adjacent Increasing Subarrays Detection IIProgramming Live with Larry · 15:13 · 434 views
3350. Adjacent Increasing Subarrays Detection II (Leetcode Medium)Programming Live with Larry · 10:09 · 404 views
LeetCode Daily 3350 | Adjacent Increasing Subarrays Detection II | Medium | Solution WalkthroughDaily Dose Of LeetCode · 16:08 · 230 views
Adjacent Increasing Subarrays Detection II | LeetCode 3350 - Pythonimpoldev · 11:17 · 199 views
3350. Adjacent Increasing Subarrays Detection II - – Optimized Solution Explained(Java) !Sneha Chauhan · 13:06 · 101 views
3350. Adjacent Increasing Subarrays Detection II | LeetCode 3350 | Intuition + Optimized Solutiondeep_dive_coding · 7:30 · 69 views
Leetcode 3350 | Adjacent Increasing Subarrays Detection II | Leetcode POTD -Multiple SolutionsAlgo Optimizers · 11:50 · 49 views
The problem
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]andnums[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
kfor 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
kfor 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.
def max_adjacent_increasing_subarrays(nums):
n = len(nums)
inc = [1] * n
for i in range(1, n):
if nums[i] > nums[i - 1]:
inc[i] = inc[i - 1] + 1
max_k = 0
for i in range(1, n):
if inc[i - 1] >= max_k and inc[i] >= max_k:
max_k = inc[i]
return max_k
nums = [2, 5, 7, 8, 9, 2, 3, 4, 3, 1]
print(max_adjacent_increasing_subarrays(nums))public class Solution {
public static int maxAdjacentIncreasingSubarrays(int[] nums) {
int n = nums.length;
int[] inc = new int[n];
inc[0] = 1;
for (int i = 1; i < n; i++) {
inc[i] = (nums[i] > nums[i - 1]) ? inc[i - 1] + 1 : 1;
}
int max_k = 0;
for (int i = 1; i < n; i++) {
if (inc[i - 1] >= max_k && inc[i] >= max_k) {
max_k = inc[i];
}
}
return max_k;
}
public static void main(String[] args) {
int[] nums = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
System.out.println(maxAdjacentIncreasingSubarrays(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxAdjacentIncreasingSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> inc(n, 1);
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) inc[i] = inc[i - 1] + 1;
}
int max_k = 0;
for (int i = 1; i < n; i++) {
if (inc[i - 1] >= max_k && inc[i] >= max_k) {
max_k = inc[i];
}
}
return max_k;
}
int main() {
vector<int> nums = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
cout << maxAdjacentIncreasingSubarrays(nums) << endl;
return 0;
}function maxAdjacentIncreasingSubarrays(nums) {
let n = nums.length;
let inc = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
inc[i] = nums[i] > nums[i - 1] ? inc[i - 1] + 1 : 1;
}
let max_k = 0;
for (let i = 1; i < n; i++) {
if (inc[i - 1] >= max_k && inc[i] >= max_k) {
max_k = inc[i];
}
}
return max_k;
}
let nums = [2, 5, 7, 8, 9, 2, 3, 4, 3, 1];
console.log(maxAdjacentIncreasingSubarrays(nums));#include <stdio.h>
int maxAdjacentIncreasingSubarrays(int* nums, int numsSize) {
if (numsSize < 2) return 0;
int inc[numsSize];
inc[0] = 1;
for (int i = 1; i < numsSize; i++) {
inc[i] = (nums[i] > nums[i-1]) ? inc[i-1] + 1 : 1;
}
int max_k = 0;
for (int i = 1; i < numsSize; i++) {
if (inc[i-1] >= max_k && inc[i] >= max_k) {
max_k = inc[i];
}
}
return max_k;
}
int main() {
int nums[] = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
int numsSize = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", maxAdjacentIncreasingSubarrays(nums, numsSize));
return 0;
}using System;
public class Solution {
public static int MaxAdjacentIncreasingSubarrays(int[] nums) {
int n = nums.Length;
int[] inc = new int[n];
inc[0] = 1;
for (int i = 1; i < n; i++) {
inc[i] = nums[i] > nums[i - 1] ? inc[i - 1] + 1 : 1;
}
int max_k = 0;
for (int i = 1; i < n; i++) {
if (inc[i - 1] >= max_k && inc[i] >= max_k) {
max_k = inc[i];
}
}
return max_k;
}
public static void Main() {
int[] nums = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
Console.WriteLine(MaxAdjacentIncreasingSubarrays(nums));
}
}The Python solution employs a list to track the length of increasing subarrays at each index, seeking adjacent subarrays with valid length for maximum k.
Time Complexity: O(n).
Space Complexity: O(n).
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.
def max_adjacent_increasing_subarrays(nums):
n = len(nums)
previous, current, max_k = 1, 1, 0
for i in range(1, n):
if nums[i] > nums[i - 1]:
current += 1
else:
previous = current
current = 1
if previous >= max_k and current > max_k:
max_k = previous
return max_k
nums = [2, 5, 7, 8, 9, 2, 3, 4, 3, 1]
print(max_adjacent_increasing_subarrays(nums))public class Solution {
public static int maxAdjacentIncreasingSubarrays(int[] nums) {
int n = nums.length;
int previous = 1, current = 1, max_k = 0;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
current++;
} else {
previous = current;
current = 1;
}
if (previous >= max_k && current > max_k) {
max_k = previous;
}
}
return max_k;
}
public static void main(String[] args) {
int[] nums = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
System.out.println(maxAdjacentIncreasingSubarrays(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxAdjacentIncreasingSubarrays(vector<int>& nums) {
int n = nums.size();
int previous = 1, current = 1, max_k = 0;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) current++;
else { previous = current; current = 1; }
if (previous >= max_k && current > max_k) max_k = previous;
}
return max_k;
}
int main() {
vector<int> nums = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
cout << maxAdjacentIncreasingSubarrays(nums) << endl;
return 0;
}function maxAdjacentIncreasingSubarrays(nums) {
let n = nums.length;
let previous = 1, current = 1, max_k = 0;
for (let i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) current++;
else { previous = current; current = 1; }
if (previous >= max_k && current > max_k) max_k = previous;
}
return max_k;
}
let nums = [2, 5, 7, 8, 9, 2, 3, 4, 3, 1];
console.log(maxAdjacentIncreasingSubarrays(nums));#include <stdio.h>
int maxAdjacentIncreasingSubarraysOptimized(int* nums, int numsSize) {
if (numsSize < 2) return 0;
int previous = 1, current = 1, max_k = 0;
for (int i = 1; i < numsSize; i++) {
if (nums[i] > nums[i-1]) {
current++;
} else {
previous = current;
current = 1;
}
if (previous >= max_k && current > max_k) {
max_k = previous;
}
}
return max_k;
}
int main() {
int nums[] = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
int numsSize = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", maxAdjacentIncreasingSubarraysOptimized(nums, numsSize));
return 0;
}using System;
public class Solution {
public static int MaxAdjacentIncreasingSubarrays(int[] nums) {
int n = nums.Length;
int previous = 1, current = 1, max_k = 0;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
current++;
} else {
previous = current;
current = 1;
}
if (previous >= max_k && current > max_k) {
max_k = previous;
}
}
return max_k;
}
public static void Main() {
int[] nums = {2, 5, 7, 8, 9, 2, 3, 4, 3, 1};
Console.WriteLine(MaxAdjacentIncreasingSubarrays(nums));
}
}The Python optimized version tracks sequence lengths using two variables, aiming for minimal space usage while maintaining time efficiency.
Time Complexity: O(n).
Space Complexity: O(1).
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).
function maxIncreasingSubarrays(nums: number[]): number {
let [ans, pre, cur] = [0, 0, 0];
const n = nums.length;
for (let i = 0; i < n; ++i) {
++cur;
if (i === n - 1 || nums[i] >= nums[i + 1]) {
ans = Math.max(ans, (cur / 2) | 0, Math.min(pre, cur));
[pre, cur] = [cur, 0];
}
}
return ans;
}func maxIncreasingSubarrays(nums []int) (ans int) {
pre, cur := 0, 0
for i, x := range nums {
cur++
if i == len(nums)-1 || x >= nums[i+1] {
ans = max(ans, max(cur/2, min(pre, cur)))
pre, cur = cur, 0
}
}
return
}impl Solution {
pub fn max_increasing_subarrays(nums: Vec<i32>) -> i32 {
let n = nums.len();
let (mut ans, mut pre, mut cur) = (0, 0, 0);
for i in 0..n {
cur += 1;
if i == n - 1 || nums[i] >= nums[i + 1] {
ans = ans.max(cur / 2).max(pre.min(cur));
pre = cur;
cur = 0;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n). |
| Approach 2: Optimized Single Pass | Time Complexity: O(n). |
| Single Pass | – |
Complexity analysis
| 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. |
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.