Continuous Subarrays — Solution in Python, Java & C++
Continuous Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Continuous Subarrays is a medium coding problem on arrays, sliding window and ordered set, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sliding Window, Ordered Set, Monotonic Queue
- 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
A contiguous, non-empty subarray of nums is called continuous when every two of its elements differ by at most 2 — that is, |nums[i1] - nums[i2]| <= 2 for every pair of indices i1, i2 inside it.
Return the total number of continuous subarrays of nums.
CodeKairo note: the original allows nums.length up to 10^5 and returns a 64-bit count; here the length is at most 5 * 10^4, so the answer fits in a 32-bit integer.
Example 1
Input: nums = [3,1,2,4,7]
Output: 9
Explanation: Five single elements, the pairs `[3,1]`, `[1,2]`, `[2,4]`, and the triple `[3,1,2]`. Every other window has a spread of at least 3.
Example 2
Input: nums = [8,8,8]
Output: 6
Explanation: All six subarrays have spread 0.
Example 3
Input: nums = [1,10]
Output: 2
Constraints
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^9
Hints for Continuous Subarrays
Hint 1
A subarray is continuous exactly when its maximum minus its minimum is at most 2.
Hint 2
If a window is continuous, so is every window inside it. For each right end, the valid left ends form a range
[left, right], andleftnever moves backwards.Hint 3
Maintain the window's max and min with two monotonic deques; shrink from the left while
max - min > 2, then addright - left + 1to the count.
How to solve Continuous Subarrays
The condition depends only on the window's extremes and is preserved under shrinking, so a two-pointer window counts, for every right end, how many left ends work.
Approach
- Keep
left = 0, a non-increasing deque for the maximum and a non-decreasing deque for the minimum. - For each
right, pushnums[right]into both deques (popping from their backs any values it dominates). - While the fronts differ by more than 2, remove
nums[left]from any deque front it occupies and advanceleft. - Every subarray
[l, right]withleft <= l <= rightis continuous — addright - left + 1.
Why it works
Adding an element can only widen the spread, so the smallest valid left for right + 1 is at least the one for right; the window therefore visits every right end with its smallest valid left end, and all left ends between that and right are valid because sub-windows of a valid window are valid. The deques keep exactly the elements that can still be a future window's maximum or minimum.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The count grows quadratically (an array of equal values has
n(n+1)/2continuous subarrays) — accumulate it in 64-bit in fixed-width languages. - Pop with strict comparisons so duplicates stay in the deques; removing by value relies on that.
- Because the spread allowed is only 2, a window holds at most three distinct values — a small ordered map of counts is an equally valid alternative to the deques.
Reference solution
Python
from typing import List
from collections import deque
def continuousSubarrays(nums: List[int]) -> int:
max_q = deque()
min_q = deque()
left = 0
ans = 0
for right, v in enumerate(nums):
while max_q and max_q[-1] < v:
max_q.pop()
max_q.append(v)
while min_q and min_q[-1] > v:
min_q.pop()
min_q.append(v)
while max_q[0] - min_q[0] > 2:
if max_q[0] == nums[left]:
max_q.popleft()
if min_q[0] == nums[left]:
min_q.popleft()
left += 1
ans += right - left + 1
return ansJava
public static int continuousSubarrays(int[] nums) {
int n = nums.length;
int[] maxQ = new int[n];
int[] minQ = new int[n];
int maxH = 0, maxT = 0, minH = 0, minT = 0, left = 0;
long ans = 0;
for (int right = 0; right < n; right++) {
int v = nums[right];
while (maxT > maxH && maxQ[maxT - 1] < v) maxT--;
maxQ[maxT++] = v;
while (minT > minH && minQ[minT - 1] > v) minT--;
minQ[minT++] = v;
while (maxQ[maxH] - minQ[minH] > 2) {
if (maxQ[maxH] == nums[left]) maxH++;
if (minQ[minH] == nums[left]) minH++;
left++;
}
ans += right - left + 1;
}
return (int) ans;
}C++
int continuousSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> maxQ(n), minQ(n);
int maxH = 0, maxT = 0, minH = 0, minT = 0, left = 0;
long long ans = 0;
for (int right = 0; right < n; right++) {
int v = nums[right];
while (maxT > maxH && maxQ[maxT - 1] < v) maxT--;
maxQ[maxT++] = v;
while (minT > minH && minQ[minT - 1] > v) minT--;
minQ[minT++] = v;
while (maxQ[maxH] - minQ[minH] > 2) {
if (maxQ[maxH] == nums[left]) maxH++;
if (minQ[minH] == nums[left]) minH++;
left++;
}
ans += right - left + 1;
}
return (int) ans;
}JavaScript
var continuousSubarrays = function(nums) {
var n = nums.length;
var maxQ = new Array(n), minQ = new Array(n);
var maxH = 0, maxT = 0, minH = 0, minT = 0, left = 0, ans = 0;
for (var right = 0; right < n; right++) {
var v = nums[right];
while (maxT > maxH && maxQ[maxT - 1] < v) maxT--;
maxQ[maxT++] = v;
while (minT > minH && minQ[minT - 1] > v) minT--;
minQ[minT++] = v;
while (maxQ[maxH] - minQ[minH] > 2) {
if (maxQ[maxH] === nums[left]) maxH++;
if (minQ[minH] === nums[left]) minH++;
left++;
}
ans += right - left + 1;
}
return ans;
};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 · Sliding Window Technique