Continuous Subarrays

medium array sliding window monotonic queue

Problem

Given an array nums, a contiguous subarray is called continuous when every pair of its elements differs by at most 2 — equivalently, its largest value minus its smallest value is ≤ 2. Return the total number of continuous subarrays.

Inputnums = [5, 4, 2, 4]

Output8

Length 1: [5],[4],[2],[4] → 4. Length 2: [5,4],[4,2],[2,4] → 3. Length 3: [4,2,4] (max−min = 2) → 1. Total = 8.

nums (comma-separated)

from collections import deque

def continuous_subarrays(nums):
    mx = deque(); mn = deque(); l = 0; total = 0
    for r, v in enumerate(nums):
        while mx and nums[mx[-1]] <= v: mx.pop()
        while mn and nums[mn[-1]] >= v: mn.pop()
        mx.append(r); mn.append(r)
        while nums[mx[0]] - nums[mn[0]] > 2:
            l += 1
            if mx[0] < l: mx.popleft()
            if mn[0] < l: mn.popleft()
        total += r - l + 1
    return total

function continuousSubarrays(nums) {
  const mx = [], mn = [];
  let l = 0, total = 0;
  for (let r = 0; r < nums.length; r++) {
    while (mx.length && nums[mx[mx.length - 1]] <= nums[r]) mx.pop();
    while (mn.length && nums[mn[mn.length - 1]] >= nums[r]) mn.pop();
    mx.push(r); mn.push(r);
    while (nums[mx[0]] - nums[mn[0]] > 2) {
      l++;
      if (mx[0] < l) mx.shift();
      if (mn[0] < l) mn.shift();
    }
    total += r - l + 1;
  }
  return total;
}

class Solution {
    public long continuousSubarrays(int[] nums) {
        Deque<Integer> mx = new ArrayDeque<>(), mn = new ArrayDeque<>();
        int l = 0; long total = 0;
        for (int r = 0; r < nums.length; r++) {
            while (!mx.isEmpty() && nums[mx.peekLast()] <= nums[r]) mx.pollLast();
            while (!mn.isEmpty() && nums[mn.peekLast()] >= nums[r]) mn.pollLast();
            mx.offerLast(r); mn.offerLast(r);
            while (nums[mx.peekFirst()] - nums[mn.peekFirst()] > 2) {
                l++;
                if (mx.peekFirst() < l) mx.pollFirst();
                if (mn.peekFirst() < l) mn.pollFirst();
            }
            total += r - l + 1;
        }
        return total;
    }
}

long long continuousSubarrays(vector<int>& nums) {
    deque<int> mx, mn;
    int l = 0; long long total = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        while (!mx.empty() && nums[mx.back()] <= nums[r]) mx.pop_back();
        while (!mn.empty() && nums[mn.back()] >= nums[r]) mn.pop_back();
        mx.push_back(r); mn.push_back(r);
        while (nums[mx.front()] - nums[mn.front()] > 2) {
            l++;
            if (mx.front() < l) mx.pop_front();
            if (mn.front() < l) mn.pop_front();
        }
        total += r - l + 1;
    }
    return total;
}

Explanation

A subarray is "continuous" when its biggest number minus its smallest number is at most 2. We want to count all such subarrays, not just find the longest one. The key observation is that continuity is monotone: if a window is valid, every sub-window inside it is valid too. So for each right endpoint we only need the leftmost start that keeps the window valid.

We slide a window with pointers l and r. As r moves right, we keep two monotonic deques of indices: mx stays decreasing in value (its front is the window max) and mn stays increasing in value (its front is the window min). When a new value arrives we pop smaller tails from mx and larger tails from mn, since they can never be the extreme again.

While nums[mx[0]] - nums[mn[0]] > 2, the window is too spread out, so we advance l and drop any deque front that has slid out of the window. Once the window is valid, every subarray ending at r and starting anywhere in [l, r] is continuous — that is exactly r - l + 1 new subarrays, which we add to the running total.

Example: nums = [5, 4, 2, 4]. At r=0 the window is [5], add 1. At r=1 the window [5,4] has diff 1, add 2 (total 3). At r=2 adding 2 makes [5,4,2] diff 3 > 2, so we shrink to [4,2] (diff 2) and add 2 (total 5). At r=3 the window [4,2,4] has diff 2, add 3 (total 8).

Each index enters and leaves each deque at most once, so the whole pass is linear even with the inner loops.

Time: O(n) Space: O(n)