Compute sliding window median
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 480. Sliding Window Median: Given an array nums and an integer k, find the median of each sliding window of size k as the window moves from left to right across the array.
https://leetcode.com/problems/sliding-window-median/description/
Quick Answer: This question evaluates the ability to maintain a running median over a sliding window, testing competencies in data structures, order statistics, dynamic updates, and algorithmic efficiency within the Coding & Algorithms domain.
Given an integer array nums and an integer k, compute the median of each contiguous subarray (sliding window) of length k as the window moves one position to the right at a time. For even k, the median is the average of the two middle elements. Return the sequence of medians as floats in the order of the window's starting index.
Constraints
- 1 <= len(nums) <= 200000
- 1 <= k <= len(nums)
- -10^9 <= nums[i] <= 10^9
- Output each median as a float (no rounding beyond standard floating-point behavior)
Hints
- Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half.
- Balance the heaps so that their sizes differ by at most one, with the lower half allowed to have one extra when k is odd.
- Use lazy deletion: mark outgoing elements in a hash map and remove them from the top of a heap only when they reach the top.
- Median is the top of the max-heap for odd k, and the average of both tops for even k.