239. Sliding Window Maximum (Hard)

Problem

Given an integer array nums and an integer k, return an array of the maximum value in every sliding window of size k.

Example

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

LeetCode 239 · Link · Hard

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, compute max per window

For each of the n - k + 1 windows, compute max(...) directly.

Python

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    return [max(nums[i:i + k]) for i in range(n - k + 1)]  # L1: n-k+1 calls, each O(k)

TypeScript

function maxSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const result: number[] = [];
    for (let i = 0; i <= n - k; i++) {                         // L1: n-k+1 iterations
        result.push(Math.max(...nums.slice(i, i + k)));        // L1: O(k) per window
    }
    return result;
}

Go

func maxSlidingWindow(nums []int, k int) []int {
  n := len(nums)
  result := []int{}
  for i := 0; i <= n-k; i++ {                               // L1: n-k+1 iterations
    maxVal := nums[i]
    for j := i + 1; j < i+k; j++ {                       // L1: O(k) per window
      if nums[j] > maxVal {
        maxVal = nums[j]
      }
    }
    result = append(result, maxVal)
  }
  return result
}

Swift

final class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var result: [Int] = []
        for start in 0...(nums.count - k) {
            var maximum = nums[start]
            for index in (start + 1)..<(start + k) { maximum = max(maximum, nums[index]) }
            result.append(maximum)
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(nums), k = window size.

Line	Per-call cost	Times executed	Contribution
L1 (max per window)	$O(k)$	n - k + 1	$O(n · k)$ ← dominates

Each max(nums[i:i+k]) must scan k elements. There are n - k + 1 windows, giving $O(n · k)$ total. No sharing of work between adjacent windows.

Complexity

• Time: $O(n · k)$, driven by L1 (max scan per window).
• Space: $O(1)$ extra (output not counted).

Approach 2: Max-heap with lazy deletion

Push (-value, index) onto a max-heap. For each new window position, pop entries whose index fell outside the window before reading the top.

Python

import heapq

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    heap = []
    result = []
    for i, x in enumerate(nums):              # L1: outer loop, n iterations
        heapq.heappush(heap, (-x, i))          # L2: O(log n) push
        if i >= k - 1:
            while heap[0][1] <= i - k:         # L3: lazy eviction loop
                heapq.heappop(heap)            # L4: O(log n) per eviction
            result.append(-heap[0][0])         # L5: O(1) read top
    return result

TypeScript

// TypeScript has no built-in heap, so we implement a min-heap.
// Storing [-value, index] gives us max-heap semantics on value.
class MinHeap {
    private data: [number, number][] = [];
    push(val: [number, number]): void {
        this.data.push(val);
        let i = this.data.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p][0] <= this.data[i][0]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
            i = p;
        }
    }
    pop(): [number, number] {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            let i = 0;
            while (true) {
                let s = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < this.data.length && this.data[l][0] < this.data[s][0]) s = l;
                if (r < this.data.length && this.data[r][0] < this.data[s][0]) s = r;
                if (s === i) break;
                [this.data[s], this.data[i]] = [this.data[i], this.data[s]];
                i = s;
            }
        }
        return top;
    }
    peek(): [number, number] { return this.data[0]; }
}

function maxSlidingWindow(nums: number[], k: number): number[] {
    const heap = new MinHeap();
    const result: number[] = [];
    for (let i = 0; i < nums.length; i++) {   // L1: outer loop, n iterations
        heap.push([-nums[i], i]);               // L2: O(log n) push
        if (i >= k - 1) {
            while (heap.peek()[1] <= i - k) {  // L3: lazy eviction loop
                heap.pop();                    // L4: O(log n) per eviction
            }
            result.push(-heap.peek()[0]);      // L5: O(1) read top
        }
    }
    return result;
}

Go

func maxSlidingWindow(nums []int, k int) []int {
  // max-heap stores [-value, index] pairs
  h := &maxHeap{}
  result := []int{}
  for i, x := range nums {                  // L1: outer loop, n iterations
    heap.Push(h, [2]int{-x, i})           // L2: O(log n) push
    if i >= k-1 {
      for (*h)[0][1] <= i-k {           // L3: lazy eviction loop
        heap.Pop(h)                   // L4: O(log n) per eviction
      }
      result = append(result, -(*h)[0][0]) // L5: O(1) read top
    }
  }
  return result
}

Swift

final class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var heap = BinaryHeap<(value: Int, index: Int)> { left, right in
            left.value == right.value ? left.index > right.index : left.value > right.value
        }
        var result: [Int] = []
        for index in nums.indices {
            heap.insert((nums[index], index))
            while let top = heap.peek, top.index <= index - k { _ = heap.removeRoot() }
            if index >= k - 1, let top = heap.peek { result.append(top.value) }
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(nums), k = window size.

Line	Per-call cost	Times executed	Contribution
L1 (loop)	$O(1)$	n	$O(n)$
L2 (heappush)	$O(log n)$	n	$O(n log n)$ ← dominates
L3/L4 (lazy eviction)	$O(log n)$ per pop	at most n total	$O(n log n)$
L5 (read top)	$O(1)$	n - k + 1	$O(n)$

Each element is pushed exactly once (L2) and popped at most once (L4). Both are $O(log n)$ per call. The heap can grow up to size n before evictions catch up, so the max heap size is $O(n)$.

Complexity

• Time: $O(n log n)$, driven by L2/L4 (n pushes and n pops, each $O(log n)$).
• Space: $O(n)$. Heap grows until elements are evicted.

Good enough to pass but noticeably slower than the optimal.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Monotonic deque (optimal)

Maintain a deque of indices whose corresponding values are strictly decreasing. The front of the deque is always the index of the current window’s maximum.

On each new index i:

1. Pop from the back while the new value beats the back value (those indices can never be the max again).
2. Push i.
3. Pop from the front if it’s outside the window (i - k).
4. Once i ≥ k - 1, record nums[deque[0]].

Python

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()
    result = []
    for i, x in enumerate(nums):             # L1: outer loop, n iterations
        while dq and dq[0] <= i - k:         # L2: evict expired front, O(1) amortized
            dq.popleft()                     # L3: O(1)
        while dq and nums[dq[-1]] < x:       # L4: remove dominated back entries
            dq.pop()                         # L5: O(1)
        dq.append(i)                         # L6: O(1) push
        if i >= k - 1:
            result.append(nums[dq[0]])       # L7: O(1) read front
    return result

TypeScript

function maxSlidingWindow(nums: number[], k: number): number[] {
    const dq: number[] = [];   // stores indices; front = max of current window
    const result: number[] = [];
    for (let i = 0; i < nums.length; i++) {          // L1: outer loop, n iterations
        while (dq.length > 0 && dq[0] <= i - k) {   // L2: evict expired front
            dq.shift();                               // L3: O(1) amortized
        }
        while (dq.length > 0 && nums[dq[dq.length - 1]] < nums[i]) {  // L4: remove dominated back
            dq.pop();                                 // L5: O(1)
        }
        dq.push(i);                                   // L6: O(1) push
        if (i >= k - 1) {
            result.push(nums[dq[0]]);                 // L7: O(1) read front
        }
    }
    return result;
}

Go

func maxSlidingWindow(nums []int, k int) []int {
  dq := []int{} // stores indices; front = index of current window max
  result := []int{}
  for i, x := range nums {                              // L1: outer loop, n iterations
    for len(dq) > 0 && dq[0] <= i-k {               // L2: evict expired front
      dq = dq[1:]                                  // L3: O(1) amortized
    }
    for len(dq) > 0 && nums[dq[len(dq)-1]] < x {   // L4: remove dominated back
      dq = dq[:len(dq)-1]                          // L5: O(1)
    }
    dq = append(dq, i)                               // L6: O(1) push
    if i >= k-1 {
      result = append(result, nums[dq[0]])         // L7: O(1) read front
    }
  }
  return result
}

Swift

final class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var deque: [Int] = [], head = 0
        var result: [Int] = []
        for index in nums.indices {
            if head < deque.count && deque[head] <= index - k { head += 1 }
            while deque.count > head, let last = deque.last, nums[last] <= nums[index] { deque.removeLast() }
            deque.append(index)
            if index >= k - 1 { result.append(nums[deque[head]]) }
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(nums), k = window size.

Line	Per-call cost	Times executed	Contribution
L1 (loop)	$O(1)$	n	$O(n)$
L2/L3 (front eviction)	$O(1)$ amortized	at most n total	$O(n)$
L4/L5 (back eviction)	$O(1)$ amortized	at most n total	$O(n)$ ← dominates with L6
L6 (append)	$O(1)$	n	$O(n)$
L7 (read front)	$O(1)$	n - k + 1	$O(n)$

Each index enters the deque exactly once (L6) and leaves at most once (L3 or L5). So across the entire run, L3 fires at most n times and L5 fires at most n times. No index is touched more than twice, giving $O(n)$ total despite the nested while loops.

Complexity

• Time: $O(n)$, driven by L1/L4/L6 (each index enters and leaves the deque at most once).
• Space: $O(k)$. The deque holds at most k indices.

Why it’s correct

If nums[j] < nums[i] for some j < i, then j can never be the window max once i is in the window, so we can safely drop it. The deque therefore always holds the “still possibly useful” indices in decreasing value order.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Per-window max	$O(n · k)$	$O(1)$
Max-heap (lazy delete)	$O(n log n)$	$O(n)$
Monotonic deque	$O(n)$	$O(k)$

The monotonic deque is the canonical answer. The same pattern solves sliding-window minimum and shows up in dynamic programming optimizations (convex-hull trick, monotonic queue DP).

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_239.py and run.
# Uses the optimal Approach 3 implementation.

from collections import deque

def max_sliding_window(nums: list, k: int) -> list:
    dq = deque()
    result = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

def _run_tests():
    assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
    assert max_sliding_window([1], 1) == [1]                    # single element
    assert max_sliding_window([1, -1], 1) == [1, -1]            # k=1, each element is its window
    assert max_sliding_window([9, 8, 7, 6, 5], 3) == [9, 8, 7] # strictly decreasing
    assert max_sliding_window([1, 2, 3, 4, 5], 3) == [3, 4, 5] # strictly increasing
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

console.assert(JSON.stringify(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) === JSON.stringify([3, 3, 5, 5, 6, 7]));
console.assert(JSON.stringify(maxSlidingWindow([1], 1)) === JSON.stringify([1]));
console.assert(JSON.stringify(maxSlidingWindow([1, -1], 1)) === JSON.stringify([1, -1]));
console.assert(JSON.stringify(maxSlidingWindow([9, 8, 7, 6, 5], 3)) === JSON.stringify([9, 8, 7]));
console.assert(JSON.stringify(maxSlidingWindow([1, 2, 3, 4, 5], 3)) === JSON.stringify([3, 4, 5]));
console.log("all tests pass");

Go

func maxSlidingWindow(nums []int, k int) []int {
  dq := []int{}
  result := []int{}
  for i, x := range nums {
    for len(dq) > 0 && dq[0] <= i-k {
      dq = dq[1:]
    }
    for len(dq) > 0 && nums[dq[len(dq)-1]] < x {
      dq = dq[:len(dq)-1]
    }
    dq = append(dq, i)
    if i >= k-1 {
      result = append(result, nums[dq[0]])
    }
  }
  return result
}

Related data structures

• Arrays, input
• Queues, deque / monotonic deque is the optimal pattern
• Heaps / Priority Queues, lazy-deletion max-heap alternative

Related concepts

• Monotonic Queue, the ordered deque pattern for maintaining a window minimum or maximum.
• Sliding Window, the contiguous range invariant behind expanding and shrinking a window.