Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 480. Sliding Window Median

Given an array and window size k, return the median of each sliding window as it moves right by one. The core challenge is maintaining the median under online insertions and deletions efficiently (O(log k) per update) for n up to 1e5—typically solved with two heaps or a balanced multiset—and for even k the median is the average of the two middle values.

Asked at:

Meta

DESCRIPTION

Input:

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

Output:

[1.0, -1.0, -1.0, 3.0, 5.0, 6.0]

Explanation: Window [1,3,-1] sorted is [-1,1,3], median is 1. Window [3,-1,-3] sorted is [-3,-1,3], median is -1. Window [-1,-3,5] sorted is [-3,-1,5], median is -1. And so on.

Constraints:

1 <= k <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
For even k, median is the average of the two middle values
Must handle online insertions and deletions efficiently

Understanding the Problem

Let's understand what we're being asked to do. We have an array like [1, 3, -1, -3, 5, 3, 6, 7] and a window size k=3. We need to slide a window of size 3 across the array and find the median of each window.

Tracing through: Window [1, 3, -1] has median 1 (middle value when sorted). Window [3, -1, -3] has median -1. Window [-1, -3, 5] has median -1. And so on.

Important constraint: For even k, the median is the average of the two middle values. For odd k, it's the single middle value. The array can have up to 1e5 elements, so we need an efficient solution.

Edge cases to consider: What if k=1 (every element is its own median)? What if the array has negative numbers? What if k equals the array length (only one window)?

Brute Force Approach

The straightforward approach is to extract each window of size k, sort it, and find the median. For each of the n-k+1 windows, we create a copy of k elements, sort them in O(k log k) time, and pick the middle element(s). This is simple to implement but inefficient because we're re-sorting mostly the same elements repeatedly.

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n * k log k) For each of n-k+1 windows, we sort k elements which takes O(k log k) time, resulting in O(n * k log k) total time

Space Complexity: O(k) We need O(k) space to store a copy of the current window for sorting

Building Intuition

As the window slides right by one position, we remove one element from the left and add one element to the right. The median changes, but most elements in the window stay the same.

The key insight is that we need to maintain the elements in sorted order within the window to quickly find the middle element(s). But we also need to efficiently handle removals and insertions as the window moves.

If we re-sort the entire window every time it moves, that's O(k log k) per window, giving us O(n * k log k) total time - too slow for n=1e5.

But if we can maintain sorted order with efficient insertions and deletions (O(log k) each), we get O(n log k) total time - much better! The challenge is finding a data structure that supports both operations efficiently.

Think about maintaining a sorted list of numbers where you frequently need to:

Find the middle element(s) quickly
Remove a specific element (the one leaving the window)
Insert a new element (the one entering the window)

Two heaps (max-heap for smaller half, min-heap for larger half) or a balanced tree structure can maintain this sorted property while supporting O(log k) insertions and deletions. The median is always at the boundary between the two halves.

Common Mistakes

Forgetting to handle even k differently - the median is the average of two middle values, not a single value

Not properly removing elements from heaps - simply deleting from a heap requires finding the element first, which can be O(k). Use lazy deletion or a balanced tree structure instead

Off-by-one errors in window boundaries - make sure to start computing medians only when the window is full (after processing k elements)

Integer overflow when computing average for even k - use (a + b) / 2.0 or a/2.0 + b/2.0 instead of (a + b) / 2

Not maintaining heap balance - the two heaps should differ in size by at most 1, requiring rebalancing after insertions/deletions

Optimal Solution

The optimal approach uses two heaps (or a balanced multiset) to maintain the window elements in sorted order. A max-heap stores the smaller half of elements, and a min-heap stores the larger half. As the window slides, we remove the outgoing element and insert the incoming element, both in O(log k) time. The median is always at the top of the heaps - either the max-heap's top (odd k) or the average of both tops (even k). This maintains sorted order without full re-sorting.

Visualization

import heapq
from collections import defaultdict
def sliding_window_median(nums, k):
    """
    Calculate median of each sliding window of size k.
    Uses two heaps to maintain median efficiently.
    """
    result = []
    
    # Max heap for smaller half (negate values for max heap)
    max_heap = []
    # Min heap for larger half
    min_heap = []
    # Track elements to be removed (lazy deletion)
    to_remove = defaultdict(int)
    
    def add_element(num):
        """Add element to appropriate heap"""
        if not max_heap or num <= -max_heap[0]:
            heapq.heappush(max_heap, -num)
        else:
            heapq.heappush(min_heap, num)
    
    def remove_element(num):
        """Mark element for lazy removal"""
        to_remove[num] += 1
        if num <= -max_heap[0]:
            # Element is in max_heap
            pass
        else:
            # Element is in min_heap
            pass
    
    def clean_heap_top(heap, is_max_heap):
        """Remove invalid elements from heap top"""
        while heap:
            top = -heap[0] if is_max_heap else heap[0]
            if to_remove[top] > 0:
                to_remove[top] -= 1
                heapq.heappop(heap)
            else:
                break
    
    def rebalance_heaps():
        """Ensure heaps are balanced (size diff <= 1)"""
        # Clean tops first
        clean_heap_top(max_heap, True)
        clean_heap_top(min_heap, False)
        
        # Rebalance if needed
        if len(max_heap) > len(min_heap) + 1:
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        elif len(min_heap) > len(max_heap):
            heapq.heappush(max_heap, -heapq.heappop(min_heap))
    
    def get_median():
        """Calculate median from heap tops"""
        clean_heap_top(max_heap, True)
        clean_heap_top(min_heap, False)
        
        if k % 2 == 1:
            # Odd k: median is max_heap top
            return float(-max_heap[0])
        else:
            # Even k: median is average of both tops
            return (-max_heap[0] + min_heap[0]) / 2.0
    
    # Build initial window
    for i in range(k):
        add_element(nums[i])
        rebalance_heaps()
    
    # Get median of first window
    result.append(get_median())
    
    # Slide window through array
    for i in range(k, len(nums)):
        # Remove outgoing element
        outgoing = nums[i - k]
        remove_element(outgoing)
        
        # Add incoming element
        incoming = nums[i]
        add_element(incoming)
        
        # Rebalance and get median
        rebalance_heaps()
        result.append(get_median())
    
    return result

start

Start sliding window median algorithm

0 / 21

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log k) For each of n elements, we perform at most two heap operations (insertion and deletion), each taking O(log k) time, resulting in O(n log k) total time

Space Complexity: O(k) We store at most k elements across both heaps (or in the balanced multiset)

What We've Learned

Two-heap median maintenance: Use a max-heap for the smaller half and min-heap for the larger half of elements to maintain O(log k) median access - this pattern applies whenever you need dynamic median queries with insertions/deletions, as direct sorting would be O(k log k) per window.
Lazy deletion with hash map: Track elements to be removed in a deletion counter map rather than immediately removing from heaps - only perform actual removal when the to-be-deleted element surfaces at a heap top, avoiding expensive O(k) heap searches while maintaining correctness.
Heap rebalancing invariant: Maintain the property that max-heap size equals min-heap size (even k) or max-heap has one extra element (odd k) - check and rebalance after every insertion and lazy deletion to ensure the median is always at the heap tops.
Integer overflow prevention: For even-sized windows, compute median as (left_max + right_min) / 2.0 rather than (left_max + right_min) / 2 to handle large integers correctly, and be careful with languages where heap operations might cause overflow when dealing with values near INT_MAX.
Sliding window with deletion pattern: This add-new, remove-old, query pattern extends beyond medians to any sliding window aggregate (kth smallest, mode, range queries) where you need efficient online updates - consider augmented data structures like balanced BSTs or indexed heaps.
Amortized complexity analysis: While individual operations might trigger multiple lazy deletions, each element is inserted once and deleted once across all windows, making the amortized time O(n log k) total rather than O(n²) - understanding amortization is crucial for analyzing streaming algorithms.

Test Your Understanding

Why is sliding-window the right data structure for this problem?

sliding-window provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2025

Meta

Senior

Late July, 2025

Meta

Senior

Early July, 2025

Meta

Senior

Get Premium to View All 8 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 480. Sliding Window Median

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact