Sliding Window Maximum Visualizer

Time and space complexity

Worked example, step by step

The same steps the simulator shows, on a small input.

1. Window size k = 3. The deque starts empty. [1, 3, -1, -3, 5, 3, 6, 7]
2. Push 1 on the back. The deque still falls from front to back.
3. 1 ≤ 3, so 1 can never be a maximum again. Pop it from the back.
4. Push 3 on the back. The deque still falls from front to back.
5. Push -1 on the back. The deque still falls from front to back.
6. Window [0..2] is full. Its maximum is the front: 3.
7. Push -3 on the back. The deque still falls from front to back.
8. Window [1..3] is full. Its maximum is the front: 3.
9. Index 1 (3) has slid out of the window. Drop it from the front.
10. -3 ≤ 5, so -3 can never be a maximum again. Pop it from the back.
11. -1 ≤ 5, so -1 can never be a maximum again. Pop it from the back.
12. Push 5 on the back. The deque still falls from front to back.
13. Window [2..4] is full. Its maximum is the front: 5.
14. Push 3 on the back. The deque still falls from front to back.
15. Window [3..5] is full. Its maximum is the front: 5.
16. 3 ≤ 6, so 3 can never be a maximum again. Pop it from the back.
17. 5 ≤ 6, so 5 can never be a maximum again. Pop it from the back.
18. Push 6 on the back. The deque still falls from front to back.
19. Window [4..6] is full. Its maximum is the front: 6.
20. 6 ≤ 7, so 6 can never be a maximum again. Pop it from the back.
21. Push 7 on the back. The deque still falls from front to back.
22. Window [5..7] is full. Its maximum is the front: 7.
23. Done: 3, 3, 5, 5, 6, 7.

Try it with your own input →

Sliding window maximum in Java, Python, C++, C and JavaScript

int[] maxSlidingWindow(int[] a, int k) {
  Deque<Integer> dq = new ArrayDeque<>();
  int[] out = new int[a.length - k + 1];
  for (int i = 0; i < a.length; i++) {
    if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
    while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
    dq.offerLast(i);
    if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
  }
  return out;
}

from collections import deque

def max_sliding_window(a, k):
    dq = deque()
    out = []
    for i in range(len(a)):
        if dq and dq[0] <= i - k:
            dq.popleft()
        while dq and a[dq[-1]] <= a[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

vector<int> maxSlidingWindow(const vector<int>& a, int k) {
  deque<int> dq;
  vector<int> out;
  for (int i = 0; i < (int)a.size(); i++) {
    if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
    while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
    dq.push_back(i);
    if (i >= k - 1) out.push_back(a[dq.front()]);
  }
  return out;
}

#include <stdlib.h>

void maxSlidingWindow(int a[], int n, int k, int out[]) {
  int *dq = malloc(n * sizeof(int)), head = 0, tail = 0;
  for (int i = 0; i < n; i++) {
    if (head < tail && dq[head] <= i - k) head++;
    while (head < tail && a[dq[tail - 1]] <= a[i]) tail--;
    dq[tail++] = i;
    if (i >= k - 1) out[i - k + 1] = a[dq[head]];
  }
  free(dq);
}

function maxSlidingWindow(a, k) {
  const dq = [];
  const out = [];
  for (let i = 0; i < a.length; i++) {
    if (dq.length > 0 && dq[0] <= i - k) dq.shift();
    while (dq.length > 0 && a[dq[dq.length - 1]] <= a[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(a[dq[0]]);
  }
  return out;
}

In an interview

LeetCode 239, Sliding Window Maximum: the largest value in every window of size k.

Store indexes, not values, so you can tell when the front has left the window. Each index enters and leaves the deque once, so the total work is O(n).

More patterns

• Sliding Window (Fixed Size) visualizer
• Sliding Window (Variable Size) visualizer
• Two Pointers (Opposite Ends) visualizer
• Container with Most Water visualizer
• Trapping Rain Water visualizer
• Fast and Slow Pointers visualizer
• Kadane's Algorithm visualizer
• Prefix Sum + Hash Map visualizer