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

Solution: Sliding Window Median

Explore how to implement the sliding window median algorithm by using two heaps to track lower and upper halves of the current window. Learn to maintain balance, handle element removal via a hash map, and optimize for time complexity close to O(n log n). This lesson guides you through an efficient solution for dynamic median calculation in arrays.

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
...