Make Lexicographically Smallest Array by Swapping Elements
You are given a 0-indexed array of positive integers nums and a positive integer limit.
In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit.
Return the lexicographically smallest array that can be obtained by performing the operation any number of times.
An array a is lexicographically smaller than an array b if, in the first position where a and b differ, array a has an element that is less than the corresponding element in b.
Example 1
Input
nums = [1,5,3,9,8], limit = 2Output
[1,3,5,8,9]After swapping
nums[1] with nums[2] and nums[3] with nums[4], the array becomes [1,3,5,8,9], and no lexicographically smaller array can be obtained.Example 2
Input
nums = [1,7,6,18,2,1], limit = 3Output
[1,6,7,18,1,2]After the described swaps, the smallest obtainable array is
[1,6,7,18,1,2].Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= limit <= 10^9