All problems

Sliding Window Median

Hard · sliding window

A list nums of whole numbers and a window size k are given. A window is k neighbouring numbers, and there is one window for each starting position from the left end to the right end of the list, so the window moves one step at a time.

The median of a window is the middle number once its numbers are put in order. If k is even there are two middle numbers, and the median is halfway between them.

To keep every answer a whole number, do not report the median itself. For each window, report the sum of its two middle numbers. When k is odd there is only one middle number, so it counts twice: report twice the median. Return these values for the windows in order, from the leftmost window to the rightmost.

Examples

Example 1

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Output: [2, -2, -2, 6, 10, 12]

The first window is 1, 3, -1. In order it is -1, 1, 3, so the middle number is 1 and we report 2. The second window is 3, -1, -3, whose middle number is -1, so we report -2.

Example 2

Input: nums = [2, 4, 6, 8], k = 2

Output: [6, 10, 14]

Each window has two numbers and both are middle numbers, so we report their sum: 2 + 4, 4 + 6 and 6 + 8.

Example 3

Input: nums = [5], k = 1

Output: [10]

Constraints