Adjacent Increasing Subarrays Detection II — Solution
Adjacent Increasing Subarrays Detection II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Adjacent Increasing Subarrays Detection II is a medium coding problem on arrays and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array nums of length n, find the largest k for which there exist two adjacent subarrays of length k that are both strictly increasing — that is, an index a such that nums[a..a + k - 1] and nums[a + k..a + 2k - 1] are both strictly increasing.
Return that maximum k. Since n >= 2, k = 1 always works.
Example 1
Input: nums = [2,5,7,8,9,2,3,4,3,1]
Output: 3
Explanation: [7,8,9] and [2,3,4] are adjacent and increasing; no `k = 4` pair exists.
Example 2
Input: nums = [1,2,3,4,4,4,4,5,6,7]
Output: 2
Explanation: Inside the run [1,2,3,4] the windows [1,2] and [3,4] work; the run [4,5,6,7] gives the same.
Example 3
Input: nums = [5,4]
Output: 1
Constraints
2 <= nums.length <= 2 * 10^5-10^9 <= nums[i] <= 10^9
Hints for Adjacent Increasing Subarrays Detection II
Hint 1
Split the array into maximal strictly increasing runs. The two windows either both fit in one run, or meet exactly at the boundary of two consecutive runs.
Hint 2
Inside one run of length
L, the best isfloor(L / 2). Across consecutive runs of lengthspandc, the best ismin(p, c).Hint 3
Keep the previous run length and the current one as you scan; update the answer with both formulas at every index.
How to solve Adjacent Increasing Subarrays Detection II
The answer is the best over two shapes: both windows inside one maximal increasing run (floor(L / 2)), or the first window ending one run and the second starting the next (min(prev, cur)). One left-to-right scan with two run lengths evaluates both.
Approach
- Set
prev = 0,cur = 1,best = 0. - For
i = 1 .. n - 1: ifnums[i] > nums[i - 1]extendcur; otherwiseprev = cur,cur = 1. - Update
best = max(best, cur / 2, min(prev, cur)). - Return
best.
Why it works
Take an optimal pair of windows. If no run break falls strictly inside the span [a, a + 2k - 1], both lie in one run of length at least 2k, caught by cur / 2. Otherwise the only break can be between the windows (each window is itself increasing), so the first is a suffix of one run and the second a prefix of the next, caught by min(prev, cur) when cur reaches that run's length. Conversely, every value the formulas produce is achievable, so the maximum is exact.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A binary search over
kwith anO(n)check also works, but is unnecessary — and the check must still handle both shapes. - Equal elements break a run (strictly increasing).
Reference solution
Python
from typing import List
def maxIncreasingSubarrays(nums: List[int]) -> int:
prev, cur, best = 0, 1, 0
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
cur += 1
else:
prev, cur = cur, 1
best = max(best, cur // 2, min(prev, cur))
return bestJava
public static int maxIncreasingSubarrays(int[] nums) {
int prev = 0, cur = 1, best = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) cur++;
else { prev = cur; cur = 1; }
best = Math.max(best, Math.max(cur / 2, Math.min(prev, cur)));
}
return best;
}C++
int maxIncreasingSubarrays(vector<int>& nums) {
int prev = 0, cur = 1, best = 0;
for (size_t i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i - 1]) cur++;
else { prev = cur; cur = 1; }
best = max(best, max(cur / 2, min(prev, cur)));
}
return best;
}JavaScript
var maxIncreasingSubarrays = function(nums) {
var prev = 0, cur = 1, best = 0;
for (var i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) cur++;
else { prev = cur; cur = 1; }
best = Math.max(best, Math.floor(cur / 2), Math.min(prev, cur));
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search