Sort a Nearly Sorted Array
Intermediate
Every value of nums is at most k positions away from the position it would have in the sorted list. Return the sorted list. Aim for O(n log k) time.
For nums = [6, 5, 3, 2, 8, 10, 9] and k = 3 the answer is [2, 3, 5, 6, 8, 9, 10].
Examples
Example 1
Input:
sort_k_sorted([6, 5, 3, 2, 8, 10, 9], 3)
Output:
[2, 3, 5, 6, 8, 9, 10]
Example 2
Input:
sort_k_sorted([3, 2, 1], 2)
Output:
[1, 2, 3]
Constraints
0 <= len(nums) <= 1000000 <= k <= len(nums)-10**9 <= nums[i] <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetheapsheap-basics
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.