Sort a K-Displaced Array
Google● MediumNEW GRADPHONE SCREENProblem statement
You are given an integer array nums and a non-negative integer k. In the fully sorted array, every input element appears at an index whose distance from its original index is at most k.
Return nums sorted in non-decreasing order. Equal values are indistinguishable.
Use the displacement guarantee to run faster than sorting all elements with a general O(n log n) comparison sort when k is much smaller than n.
Function
sortKDisplaced(nums: int[], k: int) → int[]Examples
Example 1
nums = [3,1,2,5,4]k = 2return = [1,2,3,4,5]Every value is at most two positions from its sorted location.
Example 2
nums = [1,2,3]k = 0return = [1,2,3]With displacement zero, the input is already sorted.
Example 3
nums = [2,1,2,1]k = 2return = [1,1,2,2]Duplicate values remain present.
Constraints
0 <= nums.length <= 200000.0 <= k <= max(0, nums.length - 1).-10^9 <= nums[i] <= 10^9.- The displacement guarantee is valid.