Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Sliding Window Median

Explore how to solve the sliding window median problem using an optimized heap-based approach. Understand the use of max-heaps and min-heaps to maintain window halves, the handling of outgoing elements with a hash map, and balancing heaps for median calculation. Learn to improve from a naive sorting method to an efficient O(n log n) time complexity algorithm suitable for coding interviews.

We'll cover the following...

Statement

Given an integer array, nums, and an integer, k, there is a sliding window of size k, which is moving from the very left to the very right of the array. We can only see the k numbers in the window. Each time the sliding window moves right by one position.

Given this scenario, return the median of the each window. Answers within 10−510^{-5} of the actual value will be accepted.

Constraints:

  • 1≤1 \leq k ≤\leq nums.length ≤103\leq 10^3
  • −231≤-2^{31} \leq
...