Sliding Window Maximum

Sliding Window Maximum looks easy at first. Slide a window across the array and grab the biggest number inside. But the simple way is slow. The interviewer wants to see if you can find the maximum without scanning the window again and again. That is the real test here.

🎯 The Problem

You get an array of numbers and a window size k. You slide the window across the array and note the biggest number inside each time.

• The window starts at the left and covers k numbers.
• You record the biggest number in the window.
• Then the window slides one step right and you record again.
• The window never grows or shrinks. It always holds exactly k numbers.
• The list of every window maximum is your answer.

Let us say the array is [1, 3, -1, -3, 5, 3, 6, 7] and k is 3. The first window covers 1, 3, -1. The biggest is 3. Slide right. Now the window covers 3, -1, -3. The biggest is still 3. You keep sliding and noting each maximum. The list of all these maximums is your answer.

Input:  nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]

Explanation:
Window [1, 3, -1]      max = 3
Window [3, -1, -3]     max = 3
Window [-1, -3, 5]     max = 5
Window [-3, 5, 3]      max = 5
Window [5, 3, 6]       max = 6
Window [3, 6, 7]       max = 7

Here is the same idea as a picture. The window is a frame of width k that moves one step at a time over the array.

🐢 Approach 1: Scan Each Window (Brute Force)

For every window position, scan all k numbers and pick the biggest.

The idea:

• One loop moves the window across the array.
• An inner loop scans the k numbers to find the max.

How it works:

• For each window, look at every number inside.
• Take the largest and add it to the answer.

Why it is weak:

• You scan k numbers from scratch for every window.
• Most numbers stay in the window between steps, yet you rescan them.
• Time is O(n · k). Slow when k is large.

Here is the brute-force code for that idea:

def max_sliding_window(nums, k):
    answer = []
    for left in range(len(nums) - k + 1):
        answer.append(max(nums[left:left + k]))
    return answer

🌳 Approach 2: A Max-Heap (Better)

The idea in one line: keep a heap of numbers with their positions, and the top is always the current largest.

The idea:

• A heap is a structure that hands you its largest item fast.
• Store each number together with its position.

How it works:

• Push the new number and its position into the heap.
• When you read the top, drop it first if its position has slid out of the window.
• The remaining top is the window maximum.

Why it is better:

• No inner rescan of the whole window.
• Each push and pop costs only log of the heap size.

Why it is still weak:

• The heap can hold old numbers until they bubble to the top.
• Each operation costs O(log n), so the total is O(n log n).

Here is the max-heap code for that idea:

import heapq


def max_sliding_window(nums, k):
    heap = []
    answer = []

    for i, num in enumerate(nums):
        heapq.heappush(heap, (-num, i))
        if i >= k - 1:
            while heap[0][1] <= i - k:
                heapq.heappop(heap)
            answer.append(-heap[0][0])

    return answer

⚡ Approach 3: A Monotonic Deque (Best)

The idea in one line: keep a deque of positions whose numbers decrease front to back, so the front is always the window maximum.

The idea:

• A deque is a line where you add and remove from both ends.
• Store positions, not numbers, so you can tell when one slides out.
• Keep numbers decreasing front to back. This is a monotonic deque.

How one step works:

• Drop the front position if it has slid out of the window.
• Pop smaller numbers off the back while the new number is bigger.
• Add the new position at the back.
• Once the window is full, read the front. That is the maximum.

Why it is fast:

• Each position enters the deque once and leaves once.
• So the whole scan is O(n).

Here is a dry-run of the deque as the window moves over the first few numbers. The deque holds positions but we show the numbers they point to.

Steps to Solve

1. Create an empty deque that will hold array positions.
2. Walk through the array one position at a time.
3. If the front position is older than the current window, remove it from the front.
4. While the number at the back of the deque is smaller than the current number, remove it from the back.
5. Add the current position at the back.
6. Once the window has filled (the index is at least k - 1), read the number at the front position. That is the maximum. Add it to the answer.

#include <stdio.h>

void maxSlidingWindow(int nums[], int n, int k, int out[], int *outSize) {
    int deque[100000];   // stores indices
    int head = 0, tail = 0;  // head is front, tail is one past back
    int idx = 0;
    for (int i = 0; i < n; i++) {
        // drop front index if it slid out of the window
        if (head < tail && deque[head] <= i - k) {
            head++;
        }
        // drop smaller numbers from the back
        while (head < tail && nums[deque[tail - 1]] < nums[i]) {
            tail--;
        }
        deque[tail++] = i;          // add current index at the back
        if (i >= k - 1) {           // window is full
            out[idx++] = nums[deque[head]];  // front is the max
        }
    }
    *outSize = idx;
}

int main(void) {
    int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    int out[100000];
    int outSize = 0;
    maxSlidingWindow(nums, 8, k, out, &outSize);
    printf("[");
    for (int i = 0; i < outSize; i++) {
        printf("%d", out[i]);
        if (i < outSize - 1) printf(", ");
    }
    printf("]\n");
    return 0;
}

[3, 3, 5, 5, 6, 7]

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;       // stores indices
    vector<int> result;
    for (int i = 0; i < (int)nums.size(); i++) {
        // drop front index if it slid out of the window
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // drop smaller numbers from the back
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);                 // add current index
        if (i >= k - 1) {                // window is full
            result.push_back(nums[dq.front()]);  // front is the max
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> result = maxSlidingWindow(nums, k);
    cout << "[";
    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i < (int)result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[3, 3, 5, 5, 6, 7]

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();  // stores indices
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            // drop front index if it slid out of the window
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            // drop smaller numbers from the back
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);             // add current index
            if (i >= k - 1) {            // window is full
                result[idx++] = nums[dq.peekFirst()];  // front is the max
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 3, -1, -3, 5, 3, 6, 7 };
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < result.length; i++) {
            sb.append(result[i]);
            if (i < result.length - 1) sb.append(", ");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

[3, 3, 5, 5, 6, 7]

from collections import deque


def max_sliding_window(nums, k):
    dq = deque()        # stores indices
    result = []
    for i, num in enumerate(nums):
        # drop front index if it slid out of the window
        if dq and dq[0] <= i - k:
            dq.popleft()
        # drop smaller numbers from the back
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)              # add current index
        if i >= k - 1:            # window is full
            result.append(nums[dq[0]])  # front is the max
    return result


nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))

[3, 3, 5, 5, 6, 7]

function maxSlidingWindow(nums, k) {
  const dq = []; // stores indices
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // drop front index if it slid out of the window
    if (dq.length && dq[0] <= i - k) {
      dq.shift();
    }
    // drop smaller numbers from the back
    while (dq.length && nums[dq[dq.length - 1]] < nums[i]) {
      dq.pop();
    }
    dq.push(i);                 // add current index
    if (i >= k - 1) {           // window is full
      result.push(nums[dq[0]]); // front is the max
    }
  }
  return result;
}

const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k));

[ 3, 3, 5, 5, 6, 7 ]

Let us walk through the Python version line by line and see why each line is there.

The line dq = deque() creates the empty double-ended queue. It will hold positions from the array, not the numbers. We store positions so we can tell when a position has slid out of the window.

The loop for i, num in enumerate(nums) gives us both the position i and the number num at that position. We need the position to manage the window edges.

The check if dq and dq[0] <= i - k looks at the front position. If that position is i - k or smaller, it is now too old. It sits outside the current window. So dq.popleft() drops it from the front.

The loop while dq and nums[dq[-1]] < num looks at the back. While the number at the back position is smaller than the current number, we pop it with dq.pop(). That smaller number can never be the maximum again while this bigger number is around. So it is useless. We drop it.

The line dq.append(i) adds the current position at the back. After this the deque points to numbers in decreasing order, front to back.

The check if i >= k - 1 asks if the window is full yet. The first full window ends at position k - 1. Once full, result.append(nums[dq[0]]) reads the number at the front position. The front always points to the biggest number in the window. So that is our answer for this window.

⏱️ Time and Space Complexity

The brute force scans k numbers for every window, so it is slow but needs almost no extra memory. The deque touches each position twice at most, once when it enters and once when it leaves. So it runs in one pass. That takes the time from O(n times k) down to O(n). The deque holds at most k positions, so it uses O(k) space.

🧩 Key Takeaways

• ✅ The brute force re-scans every window from scratch, which costs O(n times k) time.
• ✅ A monotonic deque stores positions whose numbers go from biggest at the front to smallest at the back.
• ✅ Drop the front position when it slides out of the window, and drop back positions that are smaller than the new number.
• ✅ The front of the deque always points to the maximum of the current window.
• ✅ Each position enters and leaves the deque once, so the whole scan is O(n) time and O(k) space.

🚀 What’s Next?

• Find All Anagrams in a String
• Max Consecutive Ones III