Sliding Window Median

Free with account Updated Nov 19, 2026 · 7 min read
On this page

    Problem statement

    Given an array of numbers and a window size k, return the median of every window of k consecutive numbers as the window slides from left to right. With an even k, the median is the average of the two middle values. Return the medians as floating-point numbers.

    The natural next step after Find Median from Data Stream: numbers now also leave. It appears in monitoring ("median latency over the last k requests") and in signal smoothing, where a running median ignores spikes that would wreck a running average. Original problem: LeetCode 480.

    Example

    With k = 3 the window covers three numbers at a time; each window's median is its middle value.
    With k = 3 the window covers three numbers at a time; each window's median is its middle value.
    Input:  nums = [5, 2, 8, 1, 9, 4], k = 3
    Output: [5.0, 2.0, 8.0, 4.0]
    Input:  nums = [5, 2, 8, 1, 9, 4], k = 2
    Output: [3.5, 5.0, 4.5, 5.0, 6.5]

    Constraints (assumed)

    • 1 ≤ k ≤ n ≤ 10⁵; values fit in a 32-bit int (including −2³¹ and 2³¹ − 1).
    • Answers within 10⁻⁵ of the true median are accepted.

    What this question tests

    • Reusing the two-heap median idea and adding deletion, which heaps don't support directly.
    • Lazy deletion, or choosing an ordered structure (balanced tree, multiset) that supports both insert and delete.
    • Numeric care: averaging two large ints without overflow.

    Questions to ask first

    1. How big are n and k? O(n · k) is fine for small windows, not for k = 10⁵.
    2. Can values repeat? (Here: yes, which matters when deleting by value.)
    3. Output type? (Here: floats, even when k is odd.)
    4. Can values reach the int limits? (Here: yes, so the even-k average must not overflow.)