Make Lexicographically Smallest Array by Swapping Elements - Solution & Explanation
Problem Statement
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 <= 109
Approach Overview
Problem 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 1: Greedy Swap Approach
This 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.
Code
Python
JavaScript
Complexity
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.
Approach 2: Segment Tree Optimization
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.
Complexity
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 3: Sorting
According to the problem description, the sorted array nums can be partitioned into several subarrays such that the difference between adjacent elements in each subarray does not exceed limit.
The lexicographically smallest array obtainable through swapping is thus the one where the elements within each subarray are sorted and placed back into their original positions in order.
We first pair each element in nums with its index to form an array of tuples, then sort by element value. We then traverse the sorted tuple array, identify the range of each subarray, sort the elements within each subarray by their original indices, and fill them back into the corresponding positions to obtain the final result.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array nums.
Complexity Comparison
| 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. |
| Sorting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Make Lexicographically Smallest Array by Swapping Elements - Leetcode 2948 - Python • NeetCodeIO • 14,003 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Make Lexicographically Smallest Array by Swapping Elements easy or hard?
Make Lexicographically Smallest Array by Swapping Elements Python/Java solution
How to solve Make Lexicographically Smallest Array by Swapping Elements in O(n)?
What is the best approach for Make Lexicographically Smallest Array by Swapping Elements?
Is Make Lexicographically Smallest Array by Swapping Elements asked at Google/Amazon/Meta?
What data structure is used in Make Lexicographically Smallest Array by Swapping Elements?
What is the time complexity of Make Lexicographically Smallest Array by Swapping Elements?
Ready to solve this problem?
Practice Make Lexicographically Smallest Array by Swapping Elements with our built-in code editor and test cases.
Practice on FleetCode