Sliding Window Median
Hard · Heap & Counting · Array · Heap (Priority Queue) · Sliding Window
Problem
The median of a list is its middle value once sorted, or the average of the two middle values when the list has even length. The median of [5, 1, 4] is 4; the median of [3, 8, 1, 6] is (3 + 6) / 2 = 4.5.
You are given an integer array nums and a window size k. A window of k consecutive elements starts at the left end and moves right one position at a time until it reaches the right end.
Return the median of every window, in order. Answers within 10^-5 of the true value are accepted.
Examples
Input: nums = [2,7,1,8,3,5], k = 3 Output: [2.0,7.0,3.0,5.0]
The windows are [2,7,1], [7,1,8], [1,8,3] and [8,3,5]; their middle values are 2, 7, 3 and 5.
Input: nums = [4,1,6,2], k = 2 Output: [2.5,3.5,4.0]
Each window has two elements, so the median is their average: 2.5, 3.5, 4.
Input: nums = [5,-3,9], k = 1 Output: [5.0,-3.0,9.0]
A window of one element is its own median.
Constraints
- 1 <= k <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Approaches
- Sort every window — time O(n · k log k), space O(k)
Follow-up
Lazy deletion is what makes heaps work for windows. With a balanced search tree (C++ multiset, Java TreeMap with counts, a sorted list) you can delete directly and keep an iterator on the middle, which is the C++ version given here. Both are O(n log k).
Related problems
Start free on Cariara · Coding problems · System design studio
