We need to slide a window of size k across the array and compute the median of each window. The median is simple to define: sort the window, pick the middle element (odd k) or average the two middle elements (even k).

The challenge is efficiency. Sorting each window from scratch costs O(k log k) per position, and with n - k + 1 windows, that becomes O(n * k log k). For n and k both near 10^5, that is far too slow.

When the window slides by one position, only one element leaves and one element enters. The k - 1 elements in the overlap keep their relative order. If we maintain a sorted structure and update it incrementally, each slide costs O(log k) for the search instead of O(k log k) for a full re-sort.

Key Constraints:

Intuition

For every window position, copy the k elements, sort them, and read the median from the middle. This translates the problem statement directly with no auxiliary data structure.

It re-sorts from scratch on every slide and discards the sorted order computed for the previous window. For small k this is fine. For large k the repeated sorting dominates the running time.

Algorithm

Example Walkthrough

Code

Since k - 1 elements stay the same between slides, the full re-sort repeats most of the work it did on the previous window. The next approach splits the window across two heaps and updates them incrementally, so each slide costs O(log k) instead of O(k log k).

Intuition

To read the median quickly, we need the window split around its middle so the middle element (or two) is always at hand. A max-heap small holds the lower half and a min-heap large holds the upper half, balanced so small has either the same count as large (even k) or exactly one more (odd k). The median is then the top of small (odd k) or the average of the two tops (even k). Adding an element is straightforward: compare it with the top of small, push it into the matching heap, and move one top across if the sizes drift apart. Removing the outgoing element is the hard part, because a heap cannot extract an arbitrary buried element in O(log k).

Lazy deletion handles the removal. Instead of physically removing the outgoing element, record it in a delayed count map. The element stays in its heap as a stale entry. Before reading either heap top, pop any stale entries that have reached the top and decrement their counts. The tops are always valid because the median only depends on the tops, and a stale entry buried below them cannot be the median while the counts stay balanced. Each element is inserted once and physically removed once, so the lazy bookkeeping adds O(log k) amortized per element.

A balance counter decides whether a rebalance is needed after each slide. The outgoing element still occupies a slot in one of the heaps, so its pending removal counts as -1 if it sits in small and +1 if it sits in large. The incoming element counts as +1 if it lands in small and -1 if it lands in large. A positive total means small holds one more element than the invariant allows, so its top moves to large. A negative total means the reverse. The two adjustments always sum to an even number, so the rebalance either moves exactly one element or does nothing.

Algorithm

Visualization and Code