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. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.
Example 1:
Input: nums = [1,5,3,9,8], limit = 2 Output: [1,3,5,8,9] Explanation: Apply the operation 2 times: - Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8] - Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9] We cannot obtain a lexicographically smaller array by applying any more operations. Note that it may be possible to get the same result by doing different operations.
Example 2:
Input: nums = [1,7,6,18,2,1], limit = 3 Output: [1,6,7,18,1,2] Explanation: Apply the operation 3 times: - Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1] - Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1] - Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2] We cannot obtain a lexicographically smaller array by applying any more operations.
Example 3:
Input: nums = [1,7,28,19,10], limit = 3 Output: [1,7,28,19,10] Explanation: [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= limit <= 109This approach utilizes a greedy method by iterating over the array and attempting to swap elements to their lexicographically smallest possible positions while respecting the limit constraint.
For each element in the array, find the smallest valid element that can be swapped to its position, keeping the |nums[i] - nums[j]| <= limit condition in mind. This is done through nested iteration for simplicity, but careful attention to the limit ensures efficiency.
The process is repeated for each element until no further swaps yield a smaller lexicographic order.
The function makeSmallest iterates over each element and finds the smallest possible element that it can be swapped with under the limit constraint. If a more optimal position is found, a swap is performed.
JavaScript
Time Complexity: O(n^2), where n is the number of elements in nums, due to nested iteration.
Space Complexity: O(1), as the solution modifies the array in place.
In this approach, a Segment Tree is used for query optimization. It allows us to efficiently determine the smallest possible element within a specific range that can swap places under the limit constraint.
As the array is processed, the Segment Tree helps find the minimal element in constant time after preprocessing, making the swapping process more efficient compared to a naive approach.
A priority queue could be used instead of a segment tree for similar effect while sometimes offering simpler implementations.
This C++ solution uses a repetitive greedy selection for swapping to achieve a lexicographically smaller array. It iteratively swaps the current element with the smallest eligible element found under the limit constraint.
C#
Time Complexity: O(n^2), due to the pair-wise swaps performed across the array.
Space Complexity: O(1), since we're modifying the array directly without additional space usage.
| Approach | Complexity |
|---|---|
| Greedy Swap Approach | Time Complexity: O(n^2), where n is the number of elements in nums, due to nested iteration. |
| Segment Tree Optimization | Time Complexity: O(n^2), due to the pair-wise swaps performed across the array. |
Make Lexicographically Smallest Array by Swapping Elements - Leetcode 2948 - Python • NeetCodeIO • 11,976 views views
Watch 9 more video solutions →Practice Make Lexicographically Smallest Array by Swapping Elements with our built-in code editor and test cases.
Practice on FleetCode