Dashboard
LC #480

Sliding Window Median

Pattern · ?AmazonGoogle

Problem

Find the median of each window of size k as it slides over an array.

Constraints

  • 1 ≤ k ≤ n ≤ 10⁵
  • -2³¹ ≤ nums[i] ≤ 2³¹ − 1

Example

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]
Why
Each window of size 3: [1,3,-1]→1, [3,-1,-3]→-1, [-1,-3,5]→-1, ...

Spot the pattern

Which pattern cracks it?

Hints

One at a time
Solve on LeetCode ↗