Skip to content

Dual Queues with Two Pointers

Lessons 1-3 used a fixed window size K. But what if the window size is dynamic -- determined by a constraint on the data itself?

That changes everything about how you manage the window. There's no K to tell you when to expire. Instead, you expand the window as long as some condition holds, and shrink it the moment that condition breaks.

The Problem

Find the longest subarray where max - min <= X.

Think about what this asks. You want a contiguous stretch of the array where the spread between the largest and smallest values stays within X. The window grows when adding the next element keeps the spread small enough. It shrinks when the spread blows past X.

To check the constraint efficiently at every step, you need O(1) access to both the current max and the current min. That means two monotonic queues running in parallel.

The Architecture

Here's the setup:

  • maxDq: a decreasing deque. The front holds the index of the current window maximum.
  • minDq: an increasing deque. The front holds the index of the current window minimum.
  • left: a pointer that marks the start of the window. It only moves right.
  • right: iterates through the array one element at a time.

For each new right:

  1. Eclipse on both deques independently. Push a[right] through maxDq (popping smaller values from the back) and through minDq (popping larger values from the back).
  2. Check the constraint: a[maxDq.front()] - a[minDq.front()] > X?
  3. If violated, advance left and expire the front of whichever deque(s) now point outside the window.
  4. Record the window size.

Two simultaneous deques: a decreasing deque tracking the window maximum and an increasing deque tracking the window minimum

Walkthrough: [1, 3, 2, 5, 1, 4], X = 2

Let's trace both deques together. I'll show values in parentheses next to indices.

right = 0, a[right] = 1: Eclipse: both deques empty. Push 0 to both. maxDq: [0(1)], minDq: [0(1)]. Max - min = 0 <= 2. Window [0, 0], size 1.

right = 1, a[right] = 3: Eclipse maxDq: back is 0(1), 1 <= 3, pop it. Push 1. maxDq: [1(3)]. Eclipse minDq: back is 0(1), 1 >= 3? No. Push 1. minDq: [0(1), 1(3)]. Max - min = 3 - 1 = 2 <= 2. Window [0, 1], size 2.

right = 2, a[right] = 2: Eclipse maxDq: back is 1(3), 3 <= 2? No. Push 2. maxDq: [1(3), 2(2)]. Eclipse minDq: back is 1(3), 3 >= 2? Yes, pop. Back is 0(1), 1 >= 2? No. Push 2. minDq: [0(1), 2(2)]. Max - min = 3 - 1 = 2 <= 2. Window [0, 2], size 3.

right = 3, a[right] = 5: Eclipse maxDq: back is 2(2), pop. Back is 1(3), pop. Push 3. maxDq: [3(5)]. Eclipse minDq: back is 2(2), 2 >= 5? No. Push 3. minDq: [0(1), 2(2), 3(5)]. Max - min = 5 - 1 = 4 > 2. Constraint violated!

Shrink: left moves from 0 to 1. Expire: maxDq front is 3 >= 1, stays. minDq front is 0 < 1, pop it. Now minDq: [2(2), 3(5)]. Max - min = 5 - 2 = 3 > 2. Still violated.

Shrink: left moves to 2. Expire: maxDq front is 3 >= 2, stays. minDq front is 2 >= 2, stays. Max - min = 5 - 2 = 3 > 2. Still violated.

Shrink: left moves to 3. Expire: maxDq front is 3 >= 3, stays. minDq front is 2 < 3, pop it. minDq: [3(5)]. Max - min = 5 - 5 = 0 <= 2. Window [3, 3], size 1.

right = 4, a[right] = 1: Eclipse maxDq: back is 3(5), 5 <= 1? No. Push 4. maxDq: [3(5), 4(1)]. Eclipse minDq: back is 3(5), 5 >= 1? Yes, pop. Push 4. minDq: [4(1)]. Max - min = 5 - 1 = 4 > 2. Violated.

Shrink: left moves to 4. Expire: maxDq front is 3 < 4, pop it. maxDq: [4(1)]. minDq front is 4, stays. Max - min = 1 - 1 = 0 <= 2. Window [4, 4], size 1.

right = 5, a[right] = 4: Eclipse maxDq: back is 4(1), pop. Push 5. maxDq: [5(4)]. Eclipse minDq: back is 4(1), 1 >= 4? No. Push 5. minDq: [4(1), 5(4)]. Max - min = 4 - 1 = 3 > 2. Violated.

Shrink: left moves to 5. Expire: maxDq front is 5, stays. minDq front is 4 < 5, pop it. minDq: [5(4)]. Max - min = 4 - 4 = 0 <= 2. Window [5, 5], size 1.

Answer: 3 (the window [0, 2] = subarray [1, 3, 2]).

The Key Insight: Synchronized Expiration, Independent Eclipse

Both deques share the same window [left, right]. That means expiration -- the front-pop that removes elements that slid out of the window -- is synchronized. When left advances, you check both fronts.

But the eclipse step is completely independent. maxDq pops values that are too small (they'll never be the max). minDq pops values that are too large (they'll never be the min). Each deque enforces its own monotonicity without caring about the other.

This separation is what makes it clean. You're not fighting two interleaved data structures. You're running two independent queues that happen to look at the same window.

Why It's O(N)

Count the operations:

  • Each element enters maxDq at most once, leaves at most once: 2N operations.
  • Each element enters minDq at most once, leaves at most once: 2N operations.
  • The left pointer only moves forward, covering at most N positions.

Total work: O(4N) = O(N). The nested while loops don't change this -- they're bounded by the total number of deque operations across all iterations.

Generalizing the Pattern

The max-minus-min constraint isn't special. This dual-queue-plus-two-pointer pattern works for any condition that depends on the window's max and/or min, as long as it has one property: once the condition breaks, expanding the window further can only make it worse.

Examples:

  • max - min <= X -- the classic version we just solved.
  • max / min <= Y (with positive values) -- the ratio grows as the spread grows.
  • Any condition that breaks monotonically -- once violated, the only fix is to shrink from the left. You'll never fix it by adding more elements on the right.

This "monotone violation" property is what makes the two-pointer approach correct. If adding an element could sometimes fix a broken constraint, you'd need to consider all possible windows, and two pointers wouldn't work.

Try It

The starter code reads N and X, then N integers. Fill in the eclipse steps for both deques. The shrink logic and expiration are already provided.

Input format: Line 1: N X Line 2: N integers

Output: the length of the longest subarray where max - min <= X.

Test with the example: 6 2 and 1 3 2 5 1 4. The answer should be 3.

Problems

Problem Link Difficulty
LC 239 — Sliding Window Maximum leetcode.com/problems/sliding-window-maximum Hard
LC 862 — Shortest Subarray with Sum at Least K leetcode.com/problems/shortest-subarray-with-sum-at-least-k Hard
LC 1438 — Longest Subarray with Abs Diff <= Limit leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit Medium
LC 1499 — Max Value of Equation leetcode.com/problems/max-value-of-equation Hard