Lexicographically Smallest Array with K-Limited Right Moves
Learn this problem
GoogleFULLTIMEPHONE SCREENProblem statement
Reorder nums into a permutation of its elements. An element originally at index j may move to any earlier index, but if it moves to a later index i, it must satisfy i - j <= k.
Return the lexicographically smallest reachable array. Equal values are treated as distinct occurrences; when two equal values are both eligible for the same output position, use the smaller original index first.
Function
smallestReachableArray(nums: int[], k: int) → int[]Examples
Example 1
nums = [3,1,2]k = 1return = [1,3,2]Value 1 may move left to the first position. The original 3 must then be placed by index 1, because moving it two places right would exceed k.
Example 2
nums = [4,3,2,1]k = 3return = [1,2,3,4]Every original element may move far enough right for the fully sorted order to be reachable.
Example 3
nums = [2,1,1]k = 0return = [2,1,1]With k = 0, no element may move right. Any leftward move would force an earlier element right, so only the original order is reachable.
Constraints
0 <= nums.length <= 2000000 <= k <= nums.length-1000000000 <= nums[i] <= 1000000000