noodleProblems/
Sort a K-Sorted Array
#121

Sort a K-Sorted Array

AlgorithmmediumHeap Priority QueueSortingArray

You are given an integer array nums that is **almost sorted**: every element is at most k positions away from its correct position in the fully sorted order. Return the array fully sorted in **non-decreasing** order.

For example, with nums = [3, 1, 2, 5, 4] and k = 2, each value is within two slots of where it belongs, and the sorted result is [1, 2, 3, 4, 5].

The point is to do better than a general sort by exploiting k: because no element travels more than k slots, the next-smallest element is always within the first k + 1 of the unplaced elements. A min-heap of size k + 1 therefore yields the sorted order in O(n log k) time.

Example cases

  • k = 2
    in nums = [3,1,2,5,4], k = 2
    out [1,2,3,4,5]
    Each value is within two positions of its sorted slot; a size-3 min-heap pops them in order.
  • k = 1
    in nums = [2,1,4,3,6,5], k = 1
    out [1,2,3,4,5,6]
    Adjacent swaps only — k = 1 means each element is off by at most one slot.
  • already sorted
    in nums = [1,2,3], k = 1
    out [1,2,3]

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= k < nums.length
  • -10^9 <= nums[i] <= 10^9
  • Each element is at most k positions away from its sorted position.
Saved
nums =
[3,1,2,5,4]
k =
2