Get started

Continuous Subarrays — Medium Problem & Solution

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…

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Sliding Window Technique