Quick Overview

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.

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/

Overview: 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

  1. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half.
  2. 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.
  3. 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.
  4. Median is the top of the max-heap for odd k, and the average of both tops for even k.

Loading coding console...

Show the approach

Approach

Maintain two heaps to represent the lower and upper halves of the current window. The lower half is a max-heap (implemented via negatives) and the upper half is a min-heap. Insertions go to one of the heaps based on value, followed by rebalancing so the size difference is at most one (with the lower half allowed one extra when k is odd). Elements leaving the window are lazily deleted: record them in a counter and physically remove them only when they reach the top of their heap. The median is either the top of the lower half (odd k) or the average of both tops (even k). This yields O(n log k) time and O(k) space.

Time complexity:
O(n log k)
Space complexity:
O(k)