Almost Sorted Restore
Problem
A sensor network delivers readings slightly out of order: each value in nums is at most k positions away from where it would be in the sorted array.
Return the readings sorted in non-decreasing order, using the fact that they are almost sorted.
Example 1
- Input:
- nums = [3, 1, 2, 6, 4, 5], k = 2
- Output:
- [1, 2, 3, 4, 5, 6]
3 belongs at index 2 (2 positions away); every other value is at most 2 positions from its place too.
Example 2
- Input:
- nums = [1, 2, 3], k = 0
- Output:
- [1, 2, 3]
Constraints
- 1 ≤ nums.length ≤ 10^5
- 0 ≤ k < nums.length
- -10^9 ≤ nums[i] ≤ 10^9
- Every value is at most k positions from its sorted position.
Hint
Show the first hint
Which elements could possibly belong at index 0 of the sorted output?
Walkthrough
How to approach it
01Clarify before coding
- Does 'k positions away' refer to the sorted position? Yes.
- Can there be duplicates? Yes; the output just needs to be non-decreasing.
- Return a new array or sort in place? A new array is fine.
02Brute force
Sort the array with a general-purpose sort and ignore the 'almost sorted' guarantee.
Cost: O(n log n). Insertion sort exploits the guarantee but costs O(n·k), which is bad for large k.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.