Adjacent Increasing Subarrays Detection I — Solution
Adjacent Increasing Subarrays Detection I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Adjacent Increasing Subarrays Detection I is an easy coding problem on arrays, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays
- 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 and an integer k, decide whether there are two adjacent subarrays of length k that are both strictly increasing.
Formally, return true if some index a exists such that nums[a..a + k - 1] and nums[a + k..a + 2k - 1] are both strictly increasing, and false otherwise. The second subarray starts right where the first one ends.
Example 1
Input: nums = [2,5,7,8,9,2,3,4,3,1], k = 3
Output: true
Explanation: [7,8,9] starts at index 2 and [2,3,4] starts at index 5 — both strictly increasing and back to back.
Example 2
Input: nums = [1,2,3,4,4,4,4,5,6,7], k = 5
Output: false
Explanation: The repeated 4s break every run, and no run is long enough.
Example 3
Input: nums = [-3,-2], k = 1
Output: true
Explanation: Every single element is a strictly increasing subarray of length 1.
Constraints
2 <= nums.length <= 1001 < 2 * k <= nums.length-1000 <= nums[i] <= 1000
Hints for Adjacent Increasing Subarrays Detection I
Hint 1
Break the array into maximal strictly increasing runs. Where can the two subarrays live?
Hint 2
Either both fit inside one run (it has length at least
2k), or the first ends a run and the second starts the next run.Hint 3
Walking left to right with the length of the previous run
prevand the current runcur, the bestkismax(cur / 2, min(prev, cur))— check it againstk.
How to solve Adjacent Increasing Subarrays Detection I
Two back-to-back strictly increasing windows of length k either sit inside one maximal increasing run of length >= 2k, or straddle the boundary between two consecutive runs, each long enough on its side. Tracking the previous and current run lengths covers both cases in one pass.
Approach
- Keep
prev = 0(length of the previous run) andcur = 1(length of the run ending here), andbest = 0. - For each
i >= 1: ifnums[i] > nums[i - 1]thencur += 1; otherwiseprev = curandcur = 1. - After each step set
best = max(best, cur / 2, min(prev, cur))(integer division). - Also apply the update once for the first element, then return
best >= k.
Why it works
If both windows lie in one run of length L, any k <= L / 2 works. If they do not, the boundary between them must coincide with a break between two runs — otherwise the windows would lie in one run — and then the first window is a suffix of the earlier run and the second a prefix of the later one, so k <= min(prev, cur). Every pair of consecutive runs is seen with cur reaching its full length, so the maximum is found.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Strictly increasing: equal neighbours end a run.
- Do not forget the case where both windows come from one long run (
cur / 2).
Reference solution
Python
from typing import List
def hasIncreasingSubarrays(nums: List[int], k: int) -> bool:
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 best >= kJava
public static boolean hasIncreasingSubarrays(int[] nums, int k) {
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 >= k;
}C++
bool hasIncreasingSubarrays(vector<int>& nums, int k) {
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 >= k;
}JavaScript
var hasIncreasingSubarrays = function(nums, k) {
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 >= k;
};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