A full sort throws away the structure you were handed. Because no element moves more than k slots, a min-heap of size k+1 always has the next smallest element on top, sorting in O(n log k) and one pass.
Updated Aug 2026 · Grounded in real Forward Deployed Engineer interview loops and written to a senior-engineer editorial bar.
A full sort throws away the structure you were handed. Because no element moves more than k slots, a min-heap of size k+1 always has the next smallest element on top, sorting in O(n log k) and one pass.
The signal is recognizing that 'each element is at most k away' bounds the window you ever need in memory, so a size-(k+1) heap suffices and a full O(n log n) sort is wasted work. The off-by-one on heap size is the thing that trips people: it must be k+1, not k, because the true next-smallest could be exactly k positions ahead. The streaming framing is the reserved follow-up, since the heap solution needs only k+1 elements buffered at any time.
No comments yet — be the first to share your approach.
