Continuous Subarrays

Medium
1357.

Continuous Subarrays

Continuous Subarrays is a medium coding problem on arrays, sliding window and ordered set, asked in Amazon and Google interviews.

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^4
  • 1 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var continuousSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • 1 <= nums[i] <= 10^9

Hints for Continuous Subarrays

  1. Hint 1

    A subarray is continuous exactly when its maximum minus its minimum is at most 2.

  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], and left never moves backwards.

  3. Hint 3

    Maintain the window's max and min with two monotonic deques; shrink from the left while max - min > 2, then add right - left + 1 to 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

  1. Keep left = 0, a non-increasing deque for the maximum and a non-decreasing deque for the minimum.
  2. For each right, push nums[right] into both deques (popping from their backs any values it dominates).
  3. While the fronts differ by more than 2, remove nums[left] from any deque front it occupies and advance left.
  4. Every subarray [l, right] with left <= l <= right is continuous — add right - 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)/2 continuous 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 ans

Java

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