Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Sliding Window Maximum
DSA

Sliding Window Maximum

Learn how to find maximum values in every sliding window efficiently using a deque.

A deque stores only the useful candidates for future windows — decreasing from front to back, so the front is always the current max.

Focus on recognizing:

“Max/min of every window” + O(n) required → monotonic deque of indices

Pattern 1: Sliding Window Maximum

[1,3,-1,-3,5,3,6,7], k=3 — watch small values get evicted so the front is always the max. Press ▶ to animate.

Sliding Window Maximum

For every window of size k sliding right across an array, report the maximum. A monotonic deque (kept strictly decreasing) stores candidate indices so the front is always the current window's max — giving O(n) total time.

Array [1,3,-1,-3,5,3,6,7], k=3. We keep a deque of indices in decreasing value order. When a bigger number arrives it kicks out all smaller ones behind it (they can never be the max again). The front index is evicted once it leaves the window. The L/R pointers are the window; the highlighted cell is its maximum. The output fills in as soon as the window has k elements.

ARRAY VISUALIZER
Steps –
1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        for i in 0..n-1:
                      
                        2
                          while deque and nums[back] < nums[i]: pop back
                      
                        3
                          push i
                      
                        4
                          if front <= i - k: pop front
                      
                        5
                          if i >= k-1: output nums[deque[0]]
                      
public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>(); // indices
    int n = nums.length;
    int[] result = new int[n - k + 1];

    for (int i = 0; i < n; i++) {
        if (!deque.isEmpty() && deque.peekFirst() <= i - k)
            deque.pollFirst();              // out of window

        while (!deque.isEmpty()
                && nums[deque.peekLast()] < nums[i])
            deque.pollLast();               // evict smaller

        deque.offerLast(i);

        if (i >= k - 1)
            result[i - k + 1] = nums[deque.peekFirst()];
    }

    return result;
}
from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                  # indices
    result = []

    for i, num in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()          # out of window

        while dq and nums[dq[-1]] < num:
            dq.pop()              # evict smaller

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;                        // indices
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();               // out of window

        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();                // evict smaller

        dq.push_back(i);

        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }

    return result;
}
function maxSlidingWindow(nums, k) {
  const dq = []; // indices
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    if (dq.length && dq[0] <= i - k) dq.shift(); // expired

    while (dq.length && nums[dq.at(-1)] < nums[i])
      dq.pop(); // evict smaller

    dq.push(i);

    if (i >= k - 1) result.push(nums[dq[0]]);
  }

  return result;
}

A value can never be a future max once something bigger arrives — evict it. Each index enters/leaves once ⇒ O(n).

Pattern 2: Sliding Window Minimum

Flip to an increasing deque — front is always the smallest in view.

Sliding Window Minimum

Find the minimum in every sliding window of size k. An increasing deque keeps the smallest at the front — evict useless larger elements.

Array: [8,5,10,7,9], k=3. Increasing deque of indices. Watch the answer array fill in as windows slide right.

ARRAY VISUALIZER
Steps –
8
0
5
1
10
2
7
3
9
4
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        deque = []                  // indices, values increasing
                      
                        2
                        for i in 0..n-1:
                      
                        3
                          while back ≥ nums[i]: pop_back   // can never be min
                      
                        4
                          push_back(i)
                      
                        5
                        if front ≤ i-k: pop_front
                      
                        6
                        i ≥ k-1 → answer front value

Flip one comparison — keep the deque increasing:

public int[] minSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        if (!deque.isEmpty() && deque.peekFirst() <= i - k)
            deque.pollFirst();

        while (!deque.isEmpty()
                && nums[deque.peekLast()] > nums[i])   // flip!
            deque.pollLast();

        deque.offerLast(i);

        if (i >= k - 1)
            result[i - k + 1] = nums[deque.peekFirst()];
    }

    return result;
}
from collections import deque

def min_sliding_window(nums, k):
    dq = deque()
    result = []

    for i, num in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()

        while dq and nums[dq[-1]] > num:   # flip!
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result
vector<int> minSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        while (!dq.empty() && nums[dq.back()] > nums[i]) // flip!
            dq.pop_back();

        dq.push_back(i);

        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }

    return result;
}
function minSlidingWindow(nums, k) {
  const dq = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    if (dq.length && dq[0] <= i - k) dq.shift();

    while (dq.length && nums[dq.at(-1)] > nums[i])
      // flip!
      dq.pop();

    dq.push(i);

    if (i >= k - 1) result.push(nums[dq[0]]);
  }

  return result;
}

Max → evict SMALLER (<). Min → evict LARGER (>). Everything else identical.

Why Store Indices, Not Values?

Indices answer two questions values cannot:

  1. Expiry — index <= i − k means it left the window.
  2. Value lookup — nums[index] gives both at once.

Storing raw values makes expiry undetectable.

Common Mistakes

Evicting equal elements with strict <.

< keeps duplicates in the deque — harmless but wasteful; use <= if you prefer tighter deques. Just stay consistent between max/min versions.

Checking expiry after pushing instead of before.

The expired index must be removed before reading peekFirst() as the answer.

Using a heap “because it’s max queries”.

O(n log k) passes, but interviews ask for the O(n) deque when they say sliding window maximum.

Complexity

MetricValue
TimeO(n) — each index pushed/popped once
SpaceO(k) — deque never exceeds window

My Private Notes

Notes are auto-saved locally to this device.