Two Heaps
LC #480Hard
Sliding Window Median
Two Heaps
AmazonGoogleProblem
Find the median of each window of size k as it slides over an array.
heapsliding-window
Constraints
- ›1 ≤ k ≤ n ≤ 10⁵
- ›-2³¹ ≤ nums[i] ≤ 2³¹ − 1
Example
Input
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3Output
[1.0, -1.0, -1.0, 3.0, 5.0, 6.0]Why
Each window of size 3: [1,3,-1]→1, [3,-1,-3]→-1, [-1,-3,5]→-1, ...