Hard

Quiz

#480 Sliding Window Median

APPROACH

The median of a sorted sequence is its middle value; for even-length sequences it is the average of the two central values (e.g., the median of [1,2,3,4] is 2.5).

A window of size k shifts one position at a time from left to right across integer array nums. After each shift, record the median of the k elements currently in the window.

Return the resulting list of medians. Answers within 10^-5 of the true value are accepted.

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 Median

--------------- -----

[1 3 -1] -3 5 3 6 7 1

1 [3 -1 -3] 5 3 6 7 -1

1 3 [-1 -3 5] 3 6 7 -1

1 3 -1 [-3 5 3] 6 7 3

1 3 -1 -3 [5 3 6] 7 5

1 3 -1 -3 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]

1 of 4

1:00

What is the optimal approach for this problem?