Combining Sliding Window with Binary Search and Heaps

Concepts: pyTwoHeapWindow, pyWindowBinarySearch, pyWindowMedian

The most common compound problem I've seen in staff-level screens is sliding window median. 'Given an array and window size K, return the median of each window.' The median is not a value you can maintain with simple addition and subtraction. You need an ordered structure. The two-heap approach -- a max-heap for the lower half and a min-heap for the upper half -- is the canonical answer. Understanding why heaps are the right structure here, and how to maintain the balance invariant as the window slides, is the kind of multi-step reasoning staff interviews are designed to test. Sliding Window Median: Two-Heap Approach The two-heap approach maintains the window as two halves: a max-heap (lo) for the smaller half and a min-heap (hi) for the larger half. The median is either the top of lo (odd