Skip to main content

480. Sliding Window Median

hard

Compute the median of every length-k window as it slides across an array. Find-median-from-data-stream plus a removal — the two-heap trick gets harder when elements actually leave.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the median array for each window in the original array. Answers within 10^-5 of the actual value will be accepted.

Constraints

  • 1 <= k <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

Examples

Example 1

Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]

Explanation: Window position [1,3,-1] → median 1. [3,-1,-3] → -1. [-1,-3,5] → -1. [-3,5,3] → 3. [5,3,6] → 5. [3,6,7] → 6.

Example 2

Input
nums = [1,2,3,4,2,3,1,4,2], k = 3
Output
[2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Find-median-from-data-stream uses two heaps: max-heap of lower half, min-heap of upper half. Median is at the boundary.

Hint 2

Here you need to also remove the element leaving the window. Heaps don't support arbitrary removal in O(log k).

Hint 3

Lazy deletion: keep a 'to-remove' counter map. When you peek a heap top, first pop any tops whose count is non-zero in the map.

Hint 4

Alternative: ordered multiset (Java TreeMap, C++ multiset, Python's SortedList from sortedcontainers). Supports add/remove/median-by-index in O(log k).

Solution approach

Reveal approach

Two-heap with lazy deletion. Maintain a max-heap 'lo' for the lower half and a min-heap 'hi' for the upper half, plus a hashmap 'toRemove' counting elements pending deletion. For each new index i: add nums[i] to the appropriate heap with rebalance, then if i >= k mark nums[i-k] for removal and adjust the heaps' notional sizes. When you read a heap top, first lazily evict: while the top has a non-zero toRemove count, pop and decrement. Rebalance the notional sizes after each step. The median is read from lo.top (odd window) or the average of lo.top and hi.top (even window). Cleaner alternative if available in your language: an ordered multiset supports O(log k) insert, delete, and index lookups directly — no lazy-deletion bookkeeping. Total O(n log k).

Complexity

Time
O(n log k)
Space
O(k)

Related patterns

  • heap
  • two-heaps
  • sliding-window
  • ordered-set

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Sliding Window Median and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →