LeetCode 480 - Sliding Window Median

The problem asks us to compute the median for every contiguous subarray, or "window", of size k as that window slides from left to right across the input array. For each position of the window, we consider exactly k elements.

leetcodehardarrayhash-tablesliding-windowheap-(priority-queue)

LeetCode Problem 480

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Sliding Window, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to compute the median for every contiguous subarray, or "window", of size k as that window slides from left to right across the input array.

For each position of the window, we consider exactly k elements. We must determine the median of those elements and append it to the result array. Once the median is recorded, the window moves one position to the right, meaning one element leaves the window and one new element enters it.

The input consists of:

  • nums, an integer array
  • k, the fixed window size

The output is an array of floating-point medians, one for each valid window position.

The key challenge is efficiency. The constraints allow nums.length up to 10^5, which means any algorithm that repeatedly sorts every window independently will likely be too slow.

A few details are especially important:

  • If the window size is odd, the median is the middle element after sorting.
  • If the window size is even, the median is the average of the two middle elements.
  • Negative numbers are allowed.
  • Duplicate values are common and must be handled correctly.
  • Since values can be as large as 2^31 - 1 or as small as -2^31, implementations must avoid overflow issues when averaging two integers.

The most difficult part of this problem is maintaining a dynamically changing ordered structure efficiently while elements continuously enter and leave the sliding window.

Important edge cases include:

  • k = 1, where every element is its own median
  • All elements identical
  • Large numbers that could overflow during averaging
  • Duplicate values that make removal from heaps tricky
  • Even-sized windows where the median is fractional
  • Strictly increasing or decreasing arrays, which stress balancing logic

Approaches

Brute Force Approach

The simplest solution is to process every window independently.

For each window:

  1. Extract the k elements.
  2. Sort them.
  3. Compute the median from the sorted list.
  4. Move the window one step to the right.

This approach is straightforward and always correct because sorting explicitly gives the exact ordering required to determine the median.

However, it is too slow for large inputs. There are O(n) windows, and sorting each window costs O(k log k). In the worst case, where k is close to n, this becomes approximately O(n^2 log n).

With n = 10^5, that complexity is infeasible.

Optimal Approach

The key observation is that we do not need to fully sort the window every time.

Instead, we only need quick access to:

  • The largest value in the lower half
  • The smallest value in the upper half

This naturally suggests using two heaps:

  • A max heap for the lower half
  • A min heap for the upper half

The median can then be obtained directly from the heap tops.

The difficulty comes from sliding windows because elements must also be removed efficiently. Standard heaps support insertion efficiently, but arbitrary removal is expensive.

To solve this, we use a technique called lazy deletion.

Instead of immediately removing elements from heaps, we record elements that should be removed in a hash map. Whenever such an element reaches the top of a heap, we discard it then.

This allows all operations to remain logarithmic.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k log k) O(k) Sort every window independently
Optimal O(n log k) O(k) Two heaps with lazy deletion

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize two heaps.

The first heap, called small, is a max heap that stores the smaller half of the window values. Since Python only provides a min heap, we store negative values to simulate a max heap.

The second heap, called large, is a normal min heap that stores the larger half of the values. 2. Maintain balancing rules.

We maintain these invariants:

  • small may contain at most one more element than large
  • Every element in small must be less than or equal to every element in large

This guarantees median extraction is simple. 3. Insert new elements.

When a new number enters the window:

  • If it belongs in the lower half, insert into small
  • Otherwise insert into large

After insertion, rebalance the heaps if necessary. 4. Remove outgoing elements lazily.

Direct heap removal is inefficient.

Instead:

  • Record outgoing elements in a hash map called delayed
  • Track logical heap sizes separately from physical heap sizes

When a delayed element reaches the top of a heap, remove it immediately. 5. Prune invalid heap tops.

Before reading a heap top, repeatedly pop while the top element is marked for deletion.

This ensures the top values are always valid window members. 6. Rebalance heaps after insertion or removal.

If one heap becomes too large:

  • Move the top element between heaps
  • Prune invalid tops if necessary
  1. Compute the median.

If k is odd:

  • The median is the top of small

If k is even:

  • The median is the average of the two heap tops
  1. Slide the window.

For each step:

  • Add the incoming value
  • Mark the outgoing value for deletion
  • Rebalance
  • Compute the new median

Why it works

The algorithm works because the two heaps always partition the window into two ordered halves.

The max heap stores the smaller half of the values, and the min heap stores the larger half. The balancing invariant guarantees that the median always lies at the heap tops.

Lazy deletion preserves correctness because elements are only ignored once they leave the window. Even though invalid elements may physically remain in the heap temporarily, pruning ensures they are never used in median calculations.

Python Solution

from typing import List
import heapq
from collections import defaultdict

class DualHeap:
    def __init__(self, k: int):
        self.small = []  # max heap via negatives
        self.large = []  # min heap

        self.delayed = defaultdict(int)

        self.small_size = 0
        self.large_size = 0

        self.k = k

    def prune(self, heap):
        while heap:
            num = -heap[0] if heap is self.small else heap[0]

            if self.delayed[num]:
                heapq.heappop(heap)
                self.delayed[num] -= 1

                if self.delayed[num] == 0:
                    del self.delayed[num]
            else:
                break

    def make_balance(self):
        if self.small_size > self.large_size + 1:
            num = -heapq.heappop(self.small)
            heapq.heappush(self.large, num)

            self.small_size -= 1
            self.large_size += 1

            self.prune(self.small)

        elif self.small_size < self.large_size:
            num = heapq.heappop(self.large)
            heapq.heappush(self.small, -num)

            self.large_size -= 1
            self.small_size += 1

            self.prune(self.large)

    def insert(self, num: int):
        if not self.small or num <= -self.small[0]:
            heapq.heappush(self.small, -num)
            self.small_size += 1
        else:
            heapq.heappush(self.large, num)
            self.large_size += 1

        self.make_balance()

    def erase(self, num: int):
        self.delayed[num] += 1

        if num <= -self.small[0]:
            self.small_size -= 1

            if num == -self.small[0]:
                self.prune(self.small)
        else:
            self.large_size -= 1

            if self.large and num == self.large[0]:
                self.prune(self.large)

        self.make_balance()

    def get_median(self) -> float:
        if self.k % 2 == 1:
            return float(-self.small[0])

        return (-self.small[0] + self.large[0]) / 2.0

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        dual_heap = DualHeap(k)

        for i in range(k):
            dual_heap.insert(nums[i])

        result = [dual_heap.get_median()]

        for i in range(k, len(nums)):
            dual_heap.insert(nums[i])
            dual_heap.erase(nums[i - k])

            result.append(dual_heap.get_median())

        return result

The implementation centers around the DualHeap helper class.

The small heap stores the lower half of values as negatives to simulate max heap behavior. The large heap stores the upper half normally.

The delayed hash map records values scheduled for removal. Since heaps do not support efficient arbitrary deletion, elements are removed only when they appear at the heap top.

The prune function repeatedly removes invalid top elements. This guarantees that any accessed heap top belongs to the current window.

The make_balance function restores the heap size invariant. The lower half may contain one extra element, but otherwise the heaps should remain balanced.

The insert function places incoming values into the appropriate heap and rebalances afterward.

The erase function logically removes outgoing values. It adjusts logical heap sizes immediately and relies on lazy deletion for actual removal.

Finally, get_median directly computes the median from the heap tops.

Go Solution

package main

import (
	"container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type DualHeap struct {
	small      *MaxHeap
	large      *MinHeap
	delayed    map[int]int
	smallSize  int
	largeSize  int
	k          int
}

func Constructor(k int) *DualHeap {
	small := &MaxHeap{}
	large := &MinHeap{}

	heap.Init(small)
	heap.Init(large)

	return &DualHeap{
		small:   small,
		large:   large,
		delayed: make(map[int]int),
		k:       k,
	}
}

func (dh *DualHeap) pruneSmall() {
	for dh.small.Len() > 0 {
		num := (*(dh.small))[0]

		if count, exists := dh.delayed[num]; exists {
			if count == 1 {
				delete(dh.delayed, num)
			} else {
				dh.delayed[num]--
			}

			heap.Pop(dh.small)
		} else {
			break
		}
	}
}

func (dh *DualHeap) pruneLarge() {
	for dh.large.Len() > 0 {
		num := (*(dh.large))[0]

		if count, exists := dh.delayed[num]; exists {
			if count == 1 {
				delete(dh.delayed, num)
			} else {
				dh.delayed[num]--
			}

			heap.Pop(dh.large)
		} else {
			break
		}
	}
}

func (dh *DualHeap) makeBalance() {
	if dh.smallSize > dh.largeSize+1 {
		num := heap.Pop(dh.small).(int)
		heap.Push(dh.large, num)

		dh.smallSize--
		dh.largeSize++

		dh.pruneSmall()

	} else if dh.smallSize < dh.largeSize {
		num := heap.Pop(dh.large).(int)
		heap.Push(dh.small, num)

		dh.largeSize--
		dh.smallSize++

		dh.pruneLarge()
	}
}

func (dh *DualHeap) insert(num int) {
	if dh.small.Len() == 0 || num <= (*(dh.small))[0] {
		heap.Push(dh.small, num)
		dh.smallSize++
	} else {
		heap.Push(dh.large, num)
		dh.largeSize++
	}

	dh.makeBalance()
}

func (dh *DualHeap) erase(num int) {
	dh.delayed[num]++

	if num <= (*(dh.small))[0] {
		dh.smallSize--

		if num == (*(dh.small))[0] {
			dh.pruneSmall()
		}
	} else {
		dh.largeSize--

		if dh.large.Len() > 0 && num == (*(dh.large))[0] {
			dh.pruneLarge()
		}
	}

	dh.makeBalance()
}

func (dh *DualHeap) getMedian() float64 {
	if dh.k%2 == 1 {
		return float64((*(dh.small))[0])
	}

	left := float64((*(dh.small))[0])
	right := float64((*(dh.large))[0])

	return (left + right) / 2.0
}

func medianSlidingWindow(nums []int, k int) []float64 {
	dh := Constructor(k)

	for i := 0; i < k; i++ {
		dh.insert(nums[i])
	}

	result := []float64{dh.getMedian()}

	for i := k; i < len(nums); i++ {
		dh.insert(nums[i])
		dh.erase(nums[i-k])

		result = append(result, dh.getMedian())
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version, but Go requires explicit heap implementations using the container/heap package.

Separate heap types are defined for min heap and max heap behavior.

Because Go does not provide automatic integer promotion during division, median computation explicitly converts operands to float64 before averaging.

Maps are used for lazy deletion exactly as in Python.

Worked Examples

Example 1

Input:

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

Since k = 3, the median is always the middle element.

Window small (max heap) large (min heap) Median
[1,3,-1] [1,-1] [3] 1
[3,-1,-3] [-1,-3] [3] -1
[-1,-3,5] [-1,-3] [5] -1
[-3,5,3] [3,-3] [5] 3
[5,3,6] [5,3] [6] 5
[3,6,7] [6,3] [7] 6

Final output:

[1,-1,-1,3,5,6]

Example 2

Input:

nums = [1,2,3,4,2,3,1,4,2]
k = 3
Window small large Median
[1,2,3] [2,1] [3] 2
[2,3,4] [3,2] [4] 3
[3,4,2] [3,2] [4] 3
[4,2,3] [3,2] [4] 3
[2,3,1] [2,1] [3] 2
[3,1,4] [3,1] [4] 3
[1,4,2] [2,1] [4] 2

Final output:

[2,3,3,3,2,3,2]

Complexity Analysis

Measure Complexity Explanation
Time O(n log k) Each insertion and removal costs logarithmic time
Space O(k) Heaps and delayed deletion map store at most window-sized data

Each element is inserted once and removed once.

Heap insertion and heap balancing operations each cost O(log k). Lazy deletion ensures that removals also remain logarithmic amortized time.

The heaps together store at most k active elements, plus a small number of delayed elements awaiting cleanup.

Test Cases

from typing import List

s = Solution()

# Example 1
assert s.medianSlidingWindow(
    [1,3,-1,-3,5,3,6,7], 3
) == [1.0,-1.0,-1.0,3.0,5.0,6.0]

# Example 2
assert s.medianSlidingWindow(
    [1,2,3,4,2,3,1,4,2], 3
) == [2.0,3.0,3.0,3.0,2.0,3.0,2.0]

# Single element array
assert s.medianSlidingWindow(
    [5], 1
) == [5.0]

# Window size equals array size
assert s.medianSlidingWindow(
    [1,2,3,4], 4
) == [2.5]

# All identical values
assert s.medianSlidingWindow(
    [2,2,2,2,2], 2
) == [2.0,2.0,2.0,2.0]

# Negative numbers
assert s.medianSlidingWindow(
    [-1,-2,-3,-4], 2
) == [-1.5,-2.5,-3.5]

# Strictly increasing sequence
assert s.medianSlidingWindow(
    [1,2,3,4,5,6], 3
) == [2.0,3.0,4.0,5.0]

# Strictly decreasing sequence
assert s.medianSlidingWindow(
    [6,5,4,3,2,1], 3
) == [5.0,4.0,3.0,2.0]

# Even window size
assert s.medianSlidingWindow(
    [1,4,2,3], 2
) == [2.5,3.0,2.5]

# Large integer values
assert s.medianSlidingWindow(
    [2147483647,2147483647], 2
) == [2147483647.0]

# Duplicate-heavy input
assert s.medianSlidingWindow(
    [1,1,1,1,1,1], 3
) == [1.0,1.0,1.0,1.0]
Test Why
Example 1 Validates standard sliding window behavior
Example 2 Verifies repeated balancing operations
Single element array Smallest valid input
Window equals array size Only one median produced
All identical values Tests duplicate handling
Negative numbers Ensures ordering works with negatives
Increasing sequence Stresses heap movement direction
Decreasing sequence Tests reverse ordering behavior
Even window size Validates average median calculation
Large integers Ensures no overflow issues
Duplicate-heavy input Tests lazy deletion correctness

Edge Cases

Window Size of One

When k = 1, every window contains exactly one element, so every element is trivially its own median.

This case can expose balancing bugs because one heap will frequently remain empty. The implementation handles this naturally because the lower heap is allowed to contain one extra element.

Duplicate Values

Duplicate values are one of the hardest aspects of this problem because heaps do not support efficient arbitrary deletion.

If multiple identical values exist, removing the wrong occurrence could corrupt the median calculation. The lazy deletion map solves this by tracking counts instead of positions. Elements are only physically removed when they reach the heap top.

Even Window Sizes

For even k, the median is the average of two middle values.

This can introduce integer division bugs or overflow issues. The implementation converts values to floating point before division, ensuring accurate decimal results and preventing overflow when summing large integers.

Large Positive and Negative Integers

The problem allows values near the 32-bit integer boundaries.

A naive implementation that averages integers before converting to floating point could overflow in some languages. Both implementations explicitly convert to floating point before division to ensure correctness.

Delayed Elements Remaining Inside Heaps

Because removal is lazy, heaps may temporarily contain invalid elements that are no longer inside the sliding window.

If these elements are not pruned correctly before median access or balancing, the algorithm can produce incorrect medians. The implementation guarantees correctness by always pruning invalid top elements before using heap tops.