AlgoMaster Logo

Continuous Subarrays

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to count every contiguous subarray where the difference between the maximum and minimum element is at most 2. Every single element qualifies on its own, so the question is how far each subarray can extend before the spread grows too large.

The condition "absolute difference between any two elements is at most 2" is equivalent to max(subarray) - min(subarray) <= 2. The max and min are the farthest-apart pair, so if their difference is within 2, every other pair is too. This reduction lets us track two values per subarray instead of comparing all pairs, and it is what makes a sliding window viable.

Two questions drive the solution: for each position, how far can the window extend while keeping max - min <= 2, and how do we maintain the min and max efficiently as elements enter and leave?

Key Constraints:

  • 1 <= nums.length <= 10^5: an O(n^2) scan can reach 10^10 operations in the worst case, so we want O(n log n) or better. The answer itself can be as large as n(n+1)/2, about 5 x 10^9, which overflows a 32-bit integer, so the count needs a 64-bit type.
  • 1 <= nums[i] <= 10^9: values fit in 32 bits, and only their differences matter, so the values themselves cause no overflow.

Approach 1: Brute Force

Intuition

Examine every subarray and check whether its spread (max - min) is within 2. For each starting index i, extend the subarray one element at a time while maintaining a running min and max. Once the spread exceeds 2, stop extending: adding elements can only widen the spread, never shrink it, so no further subarray with the same start can be valid.

Algorithm

  1. Initialize a counter count = 0.
  2. For each starting index i from 0 to n-1:
    • Set currentMin = nums[i] and currentMax = nums[i].
    • For each ending index j from i to n-1:
      • Update currentMin = min(currentMin, nums[j]) and currentMax = max(currentMax, nums[j]).
      • If currentMax - currentMin > 2, break out of the inner loop.
      • Otherwise, increment count.
  3. Return count.

Example Walkthrough

For nums = [5, 4, 2, 4]:

  • Starting at index 0 (value 5): [5] valid, [5,4] valid (spread 1), [5,4,2] invalid (spread 3). Count += 2.
  • Starting at index 1 (value 4): [4] valid, [4,2] valid (spread 2), [4,2,4] valid (spread 2). Count += 3.
  • Starting at index 2 (value 2): [2] valid, [2,4] valid (spread 2). Count += 2.
  • Starting at index 3 (value 4): [4] valid. Count += 1.
  • Total: 2 + 3 + 2 + 1 = 8.

Code

This restarts the min/max tracking from scratch for every starting index and re-scans the same elements many times. A sliding window avoids the rework: both ends only move forward, so each element is processed a constant number of times.

Approach 2: Sliding Window with Sorted Map

Intuition

Maintain a window [left, right] where the spread max - min <= 2. Expand right one step at a time, and whenever the window becomes invalid, shrink from the left until it is valid again.

Shrinking creates a problem that expanding does not. A pair of running min/max variables cannot recover the new min or max after the current min or max leaves the window, because that requires knowing which other values are still inside it.

A sorted frequency map solves this. It stores every value in the window with its count: the first key is the min, the last key is the max, and removing the departing element is a decrement (deleting the key once its count reaches zero). Languages without a sorted map can use a plain hash map and scan the keys for the min and max. Either way the map stays tiny: a valid window spans at most 3 distinct values, and inserting nums[right] adds at most one more, so the map never holds more than 4 keys.

Algorithm

  1. Initialize left = 0, count = 0, and a frequency map of the values in the window.
  2. For each right from 0 to n-1:
    • Add nums[right] to the frequency map.
    • While the spread (largest key minus smallest key) > 2, decrement the frequency of nums[left], remove the key if its count hits zero, and increment left.
    • Add (right - left + 1) to count.
  3. Return count.

Example Walkthrough

nums
1Initialize: left=0, right=0, count=0
0
left
5
right
1
4
2
2
3
4
freq
1Frequency map empty
1/7

Code

The map stays fast here only because the spread limit of 2 keeps it tiny. Two monotonic deques track the window min and max in O(n) total regardless of the spread limit, and without any sorted-container machinery.

Approach 3: Sliding Window with Monotonic Deques (Optimal)

Intuition

We can replace the sorted map with two monotonic deques: one that tracks the window minimum and one that tracks the window maximum. This is the standard technique for sliding window min/max problems.

The max deque maintains indices in decreasing order of their values. When we add a new element, we pop all indices from the back whose values are less than or equal to it, because they can never be the maximum while the new element is in the window. The front of the deque then always holds the index of the current maximum. The min deque works symmetrically.

The deques store indices rather than values for one reason: when left advances during shrinking, an index smaller than left at the front tells us that entry has fallen out of the window and must be discarded.

Algorithm

  1. Initialize left = 0, count = 0, and two deques: maxDeque and minDeque.
  2. For each right from 0 to n-1:
    • Maintain the max deque: pop from the back while the back value <= nums[right], then push right.
    • Maintain the min deque: pop from the back while the back value >= nums[right], then push right.
    • While the spread > 2, increment left and pop stale fronts from both deques.
    • Add (right - left + 1) to count.
  3. Return count.

Example Walkthrough

1Initialize: left=0, maxDeque=[], minDeque=[], count=0
0
left
5
1
4
2
2
3
4
1/7

Code