Solution: Sliding Window Median

Explore how to solve the sliding window median problem by implementing heaps to efficiently manage two halves of the data. Understand the optimized approach that balances max-heap and min-heap operations to compute medians with logarithmic time complexity. This lesson helps you handle incoming and outgoing elements dynamically while maintaining performance using a hash map for delayed removals. By the end, you'll be able to apply these techniques to similar dynamic median calculations in coding interviews.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using heaps

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^{-5}$ of the actual value will be accepted.

Constraints:

$1 \leq$ k $\leq$ nums.length $\leq 10^3$
$-2^{31} \leq$

...