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 keeps the window in a structure that supports an incremental update, so each slide costs O(log k) instead of O(k log k).

Intuition

To read the median quickly, we need the window kept in sorted order so the middle element (or two) is always available. Two structures support an incremental update in O(log k) for the search:

Two heaps. Split the window into a max-heap small holding the lower half and a min-heap large holding 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 routes it to the correct heap. Removing one is harder, 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 balanced sorted container. Languages with an ordered multiset (C++ multiset) support insert, erase, and an iterator to the middle, all near O(log k). The implementations below use the natural structure for each language: heaps for Java, Python, and Rust; a multiset with a tracked middle iterator for C++; and a sorted array for C#, Go, JavaScript, and TypeScript. The sorted-array versions binary-search in O(log k) to find the position but shift elements in O(k) to insert or remove, so their per-slide cost is O(k) rather than O(log k). They are shorter and pass within the constraints, but they are asymptotically slower than the heap and multiset versions.

Algorithm

Example Walkthrough

Code