Sort a K Sorted Array
A medium Sorting problem included in Love Babbar 450. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Sorting
- Sheets
- 1
- Core for
- 13 roles
- Platform
- GeeksforGeeks
The problem
Given an array that is almost sorted, where each element is at most k positions away from its sorted position, sort it efficiently.
Example 1
- Input
- nums = [6, 5, 3, 2, 8, 10, 9], k = 3
- Output
- [2, 3, 5, 6, 8, 9, 10]
- Why
- Each element is at most 3 positions away from where it should be in the sorted array.
Example 2
- Input
- nums = [2, 1, 3, 1, 2], k = 1
- Output
- [1, 1, 2, 2, 3]
Constraints
- 1 <= nums.length <= 10^5
- 0 <= k <= nums.length
- -10^5 <= nums[i] <= 10^5
How to think about it
Updated 2026-09-09The guarantee that every item is at most k steps away means the true global minimum cannot hide in the distant tail; it must sit somewhere in the first k + 1 items. By maintaining a sliding window of size k + 1 in a min-heap, extracting the minimum always produces the definitive next element of the sorted output.
Approaches, worst first
Unconstrained full sort
time O(n log n) · space O(1)
Ignore the distance parameter k and sort the entire array with standard quicksort or timsort. Simple, but pays O(n log n) overhead by failing to capitalize on the strong locality guarantee.
Insertion sort within window
time O(n * k) · space O(1)
Run insertion sort knowing each element shifts backward at most k steps. Each insertion takes O(k) comparisons, yielding an O(n * k) overall runtime that is very fast for tiny k but degrades if k scales toward n.
Min-heap sliding windowWrite this one
time O(n log k) · space O(k)
Push the first k + 1 elements into a min-heap. Pop the minimum to write to the result, push the next input element, and repeat until the array is consumed, then drain the heap. The heap never exceeds k + 1 elements.
Where people lose marks · 3
- Sizing the initial heap to k instead of k + 1: an element at index k could belong at index 0, so the candidate pool for the first position requires all k + 1 initial items.
- When k = 0, the array is already sorted; handling k = 0 with a window of size 1 must not crash or trigger empty heap access.
- Forgetting to empty the remaining items from the min-heap after reaching the end of the input array leaves the final k elements missing from the sorted output.
The theory behind it
Sorting — the ground this problem stands on. All Sorting problems
What Sorting is
Sorting is the act of arranging a scrambled hand of playing cards into ascending rank from left to right. It reorganizes scattered data according to a consistent comparison rule, like numbering index cards or alphabetizing names. While unsorted data requires searching every single entry to verify whether an item exists, ordered data establishes predictable relationships that make duplicates, clusters, and extreme values immediately visible.
When to reach for it
Reach for sorting when a problem asks to group identical items, detect overlaps among intervals, find rank percentiles, or pair values matching a target sum. If an unordered problem appears intractable in polynomial time, sorting the input frequently unlocks linear scans or two-pointer sweeps. When an O(n log n) preprocessing step simplifies downstream matching logic, sorting is usually the right opening move.
How the pattern works
Think of sorting as a trade: invest logarithmic overhead upfront to make subsequent queries direct and orderly. Compare adjacent elements to uncover duplicate entries, or march inward from outer boundaries once elements stand in monotonic sequence. When designing custom comparators, confirm strict weak ordering by verifying reflexivity, antisymmetry, and transitivity; inconsistent comparison logic breaks internal pivot partitions or produces corrupted outputs.
What each operation costs
| Operation | Time |
|---|---|
| sort using comparison based algorithms | O(n log n) |
| sort bounded integers using count buckets | O(n + k) |
| sort using quadratic bubble or selection | O(n^2) |
What usually goes wrong with Sorting
- Writing comparator functions that return inconsistent ordering results, violating transitive rules and leading to infinite loops or crashes during library sorting.
- Sorting in-place when original array indices must be returned in the final answer, destroying initial positions without keeping index-value pairings beforehand.
- Assuming default language sorting sorts numbers numerically when some environments convert arguments to strings first, sorting ten ahead of two.
Which roles need this problem
Sorting is a core topic for these 13 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 13 more roles, including ML Engineer, Android Developer, iOS Developer.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Sorting problems
Problem set and role mapping as of .