Watch 10 video solutions for Make Lexicographically Smallest Array by Swapping Elements, a medium level problem involving Array, Union Find, Sorting. This walkthrough by NeetCodeIO has 13,767 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: You are given an array nums and a limit value. You may swap two elements if their absolute difference is ≤ limit. The goal is to perform any number of valid swaps so the final array is lexicographically smallest.
Approach 1: Greedy Swap with Value Grouping (O(n log n) time, O(n) space)
The key observation: if two numbers can swap directly or through a chain of swaps, they belong to the same connected group. Sort pairs (value, index) by value, then scan and group elements where adjacent value differences are ≤ limit. Inside each group, the values can be freely rearranged. Collect the indices from that group, sort the indices, and place the smallest values into the smallest positions to minimize lexicographic order. This approach uses sorting and greedy placement to build the smallest possible prefix at every step.
Approach 2: Union-Find Component Construction (O(n log n) time, O(n) space)
You can model the swap rule as a graph where indices are connected if their values differ by ≤ limit. After sorting values, union adjacent elements that satisfy the constraint using Union Find. Each connected component represents indices that can freely swap. For each component, gather its indices and values, sort both lists, and assign the smallest values to the smallest indices. This formalizes the connectivity idea and works well when thinking about transitive swaps.
Approach 3: Segment Tree Optimization (O(n log n) time, O(n) space)
When handling large arrays or frequent queries about valid placements, a segment tree can track available indices while assigning values. After grouping values that can interact, store free positions in a tree structure and repeatedly place the smallest value into the leftmost available valid index. The tree supports fast updates and queries in O(log n). This approach combines array manipulation with ordered placement for efficient large-scale operations.
Recommended for interviews: The greedy grouping solution is the expected answer. It shows you recognize that the swap rule creates connected components and that sorting values inside each component minimizes lexicographic order. Explaining the union-find interpretation demonstrates deeper algorithmic understanding, but the greedy sorted grouping approach is simpler to implement during an interview.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Swap with Value Grouping | O(n log n) | O(n) | Best general solution. Simple implementation using sorting and grouping. |
| Union-Find Components | O(n log n) | O(n) | Useful when modeling swaps as connectivity problems or when practicing union-find patterns. |
| Segment Tree Optimization | O(n log n) | O(n) | Helpful for large inputs or when efficient index allocation queries are needed. |