Nearly sorted
Min-heap of size k+1 — a sliding window of candidates
The k-sorted promise is the whole algorithm: if a value belongs at position w, it cannot currently sit further right than w + k. Turn that around and the value that belongs at position w must already be among the first k+1 unplaced values — everything beyond them is too far right to reach position w. So keep exactly k+1 values in a min-heap, pop the root to fill the next answer slot, and read one fresh value in to refill the window. The heap never grows past k+1, so each of the n values costs log k instead of log n.
Details
Animated on: nums = [5,3,2,8,6,10,9], k = 2 — every value is at most 2 positions from its sorted place. Sort it without paying for a full O(n log n) sort.
Problem:Nearly sortedMedium
Min-heap of size k+1 — a sliding window of candidates
step 1 / 9
nums=[5,3,2,8,6,10,9] is already nearly sorted: every value sits at most k=2 places from where it belongs. A full sort would pay O(n log n) and ignore that promise. Instead watch only a window of k+1=3 values — the true smallest can never be hiding further right than that.
1FUNCTION sortKSorted(nums, k):2 heap <- empty MIN-HEAP3 out <- empty list4 FOR i <- 0 TO k:5 PUSH nums[i] INTO heap6 FOR i <- k + 1 TO LENGTH(nums) - 1:7 APPEND POP-MIN(heap) TO out8 PUSH nums[i] INTO heap9 WHILE heap NOT EMPTY:10 APPEND POP-MIN(heap) TO out11 RETURN out
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- nums=[5,3,2,8,6,10,9] is already nearly sorted: every value sits at most k=2 places from where it belongs. A full sort would pay O(n log n) and ignore that promise. Instead watch only a window of k+1=3 values — the true smallest can never be hiding further right than that.
- The first 3 values [5,3,2] go into a min-heap, which parks itself in the shaded cells as [2,5,3] — heap order, so the root 2 is the smallest of them. Position 0 in the answer belongs to whichever value is smallest overall, and anything still unread starts at index 3, which is more than k=2 away from position 0 — so no unread value can claim it. The root wins by elimination.
- The root 2 was the smallest of the 3 live candidates, so it is locked into position 0. Reading nums[3]=8 refills the window back to 3; it sifts into the heap, which is now [3,5,8] with 3 on top. Answer so far: [2].
- The root 3 was the smallest of the 3 live candidates, so it is locked into position 1. Reading nums[4]=6 refills the window back to 3; it sifts into the heap, which is now [5,8,6] with 5 on top. Answer so far: [2,3].
- The root 5 was the smallest of the 3 live candidates, so it is locked into position 2. Reading nums[5]=10 refills the window back to 3; it sifts into the heap, which is now [6,8,10] with 6 on top. Answer so far: [2,3,5].
- The root 6 was the smallest of the 3 live candidates, so it is locked into position 3. Reading nums[6]=9 refills the window back to 3; it sifts into the heap, which is now [8,10,9] with 8 on top. Answer so far: [2,3,5,6].
- Nothing is left to read, so the window only shrinks now. 8 was the root, so it takes position 4; 2 values remain in the heap as [9,10].
- Nothing is left to read, so the window only shrinks now. 9 was the root, so it takes position 5; one value remains in the heap as [10].
- The last value 10 lands in position 6 and the heap is empty: [2,3,5,6,8,9,10]. The heap never held more than k+1=3 values, so every push and pop cost log(3) instead of log(7) — O(n log k) time and O(k) space, which for a small k is close to a single linear sweep.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.