Skip to content

Volume ITechnology

4.6.6 — Sliding Window Maximum ​

LeetCode 239 · Hard

The problem ​

You are given a list of numbers nums and a window size k. A window of k numbers starts at the left end and slides right, one step at a time, until it reaches the right end. For every position of the window, report the biggest number inside it.

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

[1  3  -1] -3  5  3  6  7    →  3
 1 [3  -1  -3] 5  3  6  7    →  3
 1  3 [-1  -3  5] 3  6  7    →  5
 1  3  -1 [-3  5  3] 6  7    →  5
 1  3  -1  -3 [5  3  6] 7    →  6
 1  3  -1  -3  5 [3  6  7]   →  7

answer: [3, 3, 5, 5, 6, 7]

The list has up to 100,000 numbers, which can be negative. k is between 1 and the length of the list.

What the problem is really asking ​

Each slide adds one number on the right and removes one on the left. Adding is easy: compare the new number with the current biggest. Removing is the hard part. If the number leaving was the biggest, what is the new biggest? You would have to look through the whole window again.

So the real question is: how do you keep track of the maximum when numbers keep leaving from the other end?

The brute force, and where it wastes work ​

For each window, scan its k numbers for the biggest.

python
def maxSlidingWindow(nums, k):
    return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]

That is O(n \cdot k). With n = 100{,}000 and k = 50{,}000, it is billions of steps.

The waste in one sentence: neighbouring windows share k - 1 numbers, but each scan starts from scratch and forgets everything it learned.

The idea ​

Here is the observation that unlocks an O(n) answer.

If a smaller number arrived before a bigger number, the smaller one can never be the window's maximum again.

Why? The bigger number arrived later, so it will stay in the window for at least as long as the smaller one. Every future window that still contains the smaller number also contains the bigger one. So the smaller number is useless from now on, and we can forget it.

Think of students walking into a classroom while older students leave from the other door, and you want to know the tallest student in the room. A very tall student walks in. Every shorter student who arrived earlier will leave before this one does. So none of them can ever be the tallest in the room again. We stop keeping track of them.

If we keep throwing away useless numbers like this, the ones left over are always in decreasing order from oldest to newest. The oldest one, at the front, is the biggest. That is the window's maximum.

The structure that holds them is a deque, pronounced "deck", short for "double-ended queue". It is a list that lets you add and remove at both ends in constant time. We use the back to add new numbers and throw away smaller ones. We use the front to read the maximum, and to remove it once it slides out of the window. A deque whose contents always go in one direction like this is called a monotonic deque. "Monotonic" means "always moving one way", here always decreasing.

We store positions, not the numbers themselves. A position tells us when an entry has slid out of the window. A number alone cannot.

deque holds indices, values shown for clarity — always decreasing front to back3-1-3front = current maxthese are smaller AND older5 arrives5everything smaller was evicted from the back−1 and −3 can never win again: 5 is in every remaining window that contains them,and 5 leaves later than they do. So they are useless and get dropped.
The deque keeps only the values that could still become the maximum.

The solution ​

python
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()                                   # (1)
        result = []

        for i in range(len(nums)):                     # (2)
            if dq and dq[0] <= i - k:                  # (3)
                dq.popleft()

            while dq and nums[dq[-1]] < nums[i]:       # (4)
                dq.pop()

            dq.append(i)                               # (5)

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

        return result
ts
function maxSlidingWindow(nums: number[], k: number): number[] {
  const dq: number[] = [];                             // (1)
  let head = 0;                                        // front of the deque
  const result: number[] = [];

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

    while (dq.length > head && nums[dq[dq.length - 1]] < nums[i]) {  // (4)
      dq.pop();
    }

    dq.push(i);                                        // (5)

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

  return result;
}

Line by line ​

(1) The deque. It holds positions in the list. The numbers at those positions always decrease from front to back.

In Python, collections.deque removes from the front in constant time. A plain Python list with pop(0) does not. It shifts every other item down by one, which costs up to k steps, and that would turn this into the slow solution again.

JavaScript arrays have the same problem with shift(). So the TypeScript version never really removes from the front. It keeps a number head that marks where the front is, and moves head forward instead. Everything before head is treated as gone.

(2) Visit each position i in turn. Position i is the right edge of the current window. The window covers positions i - k + 1 to i.

(3) Drop the front if it has slid out. The front position is outside the window when it is i - k or smaller. Only one position leaves per step, so one check is enough. This is an if, not a while.

(4) Throw away smaller numbers from the back. While the number at the back is smaller than the new number, it can never be the maximum again, so we remove it. When this loop ends, everything left is at least as big as nums[i], so adding i keeps the order decreasing.

We use <, not <=. With <=, an equal number would also be thrown away. The answer would still be right, but keeping equal numbers is simpler to reason about and costs nothing.

(5) Add the new position at the back. It might become the maximum later, after the bigger numbers in front of it slide out.

(6) Report the maximum once the first full window exists. The first window covers positions 0 to k - 1. So from i = k - 1 onward, every step completes a window, and the front of the deque is its maximum.

Trace ​

Take nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3. The deque is shown as the numbers at its positions, front first.

inums[i]Front slid out?Thrown from backDeque afterOutput
01——[1](window not full)
13—1[3](window not full)
2−1——[3, −1]3
3−3no—[3, −1, −3]3
45yes, the 3 at position 1−3, −1[5]5
53——[5, 3]5
66—3, 5[6]6
77—6[7]7

The answer is [3, 3, 5, 5, 6, 7]. ✓

Look at row 4. The 3 at the front was at position 1, and the window now covers positions 2 to 4, so it slid out. Then the new 5 threw away both −3 and −1, because they arrived earlier and are smaller.

Complexity, derived ​

Time. Again there is a while loop inside a for loop, and again it is not O(n^2). Count the total work over the whole run.

  • Each position is added to the deque exactly once, in line (5). That is n additions in total.
  • Each position is removed at most once, either from the back in line (4) or from the front in line (3). A position that has been removed is never added again. So there are at most n removals in total.

So the deque does at most 2n operations over the entire run, each in constant time. Everything else is constant work per step. The total is O(n).

Space. The deque only holds positions inside the current window, so at most k of them. The extra memory is O(k), not counting the answer list.

Edge cases ​

  • k = 1. Every window is one number, so the answer is the list itself. The code handles it: each new number throws out the previous one or the front slides out.
  • Numbers only go down, like [5, 4, 3, 2, 1]. Nothing is ever thrown from the back. The deque grows to k entries, and the front slides out each step.
  • Numbers only go up, like [1, 2, 3, 4, 5]. Each new number throws out everything. The deque never holds more than one entry.
  • Repeated numbers, like [2, 2, 2]. Because line (4) uses <, equal numbers stay. The front slides out on time, and the next equal number takes over.

The heap version, for comparison ​

A heap is a structure that always keeps its biggest (or smallest) item at the top. You can push every number with its position into a heap that keeps the biggest on top. Before reading the top, throw away any top entry whose position has slid out of the window.

That is O(n \log k) time, because each push or pop on a heap costs O(\log k). Old entries may linger deep inside the heap until they reach the top, so the memory can grow to O(n). It is easier to write and a perfectly good first answer. The deque is the one that reaches O(n).

Variations you will meet ​

  • Sliding window minimum. Flip the comparison in line (4) to >. The deque then keeps increasing numbers, and the front is the smallest.
  • Jump Game VI. At each position you may jump up to k steps back, and you want the best total score. The best score at a position needs the biggest score among the last k positions. A monotonic deque gives that in constant time per step, turning an O(n \cdot k) solution into O(n).
  • Shortest Subarray with Sum at Least K. With negative numbers, a plain window breaks. The answer combines running totals with a monotonic deque.

The general lesson: when you need the biggest or smallest value over a range that slides forward, a monotonic deque gives it in constant time per step. That is why this problem is worth the effort. It is a building block for harder problems.

What the interviewer will push on ​

"Why is this O(n) when there is a loop inside a loop?" Each position enters the deque once and leaves at most once, so the total deque work is at most 2n.

"Why store positions instead of numbers?" You need to know when an entry has slid out of the window, and only the position tells you that.

"Why < and not <= when throwing away?" Either works. With <, equal numbers are kept, which is simpler to reason about.

"Could you use a heap?" Yes, O(n \log k), removing stale entries when they reach the top. Say that, then say why the deque is faster.

"What if you needed the minimum instead?" Flip the comparison. Answering that instantly shows you understood the structure, not just this problem.

One thing to volunteer: say the throw-away rule as a sentence. "A smaller number that arrived earlier can never be the maximum again, because the bigger, later number outlasts it." Everything in the code follows from that.

Next: 4.7 Linked Lists, Stacks and Queues. It covers the structures behind this deque, and the stack that the next group of problems is built on.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet