Sliding Window Median

HardHeaptwo heaps

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

The **median** of a group of numbers is the value that sits exactly in the middle once the numbers are arranged in sorted order. When the group contains an odd count of numbers, the median is the single middle value. When it contains an even count, the median is the average of the two middle values. For example: - The median of [2, 3, 4] is 3. - The median of [1, 2, 3, 4] is (2 + 3) / 2 = 2.5. You are given an integer array nums and an integer k. A window of size k starts at the leftmost end of the array and slides one position to the right at each step, until it reaches the rightmost end. At every position, the window covers exactly k consecutive elements of nums. Return an array result where result[i] is the median of the i-th window, in order from the first window to the last. Because medians of even-sized windows can be fractional, return the answers as double values. There are len(nums) - k + 1 windows in total, so result will contain that many entries.

Examples

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]
The windows in order are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]. Sorting each gives medians 1, -1, -1, 3, 5, 6.
Input: nums = [1,2,3,4], k = 2
Output: [1.5, 2.5, 3.5]
The windows are [1,2], [2,3], [3,4]. Each window has an even size, so the median is the average of its two values.
Input: nums = [5], k = 1
Output: [5.0]
There is a single window containing only 5, and its median is 5.

Constraints

  • 1 <= k <= len(nums) <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • Answers should be accurate to within 1e-5 of the true median.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.