Make Lexicographically Smallest Array by Swapping Elements
Make Lexicographically Smallest Array by Swapping Elements is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (sort, then split into gap groups), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (union-find over all pairs) up.
Problem
You are given an array of positive integers nums and a positive integer limit. In one move you may pick any two indices i and j and swap nums[i] and nums[j], but only if |nums[i] - nums[j]| <= limit. You may make as many moves as you like.
Return the lexicographically smallest array you can reach. An array is lexicographically smaller than another of the same length if, at the first index where they differ, it holds the smaller value.
Examples
Example 1
- Input
nums = [4, 9, 2, 10, 1], limit = 2- Output
[1, 9, 2, 10, 4]- Why
- 1, 2 and 4 can reach each other through 2, so they are sorted into indices 0, 2, 4; 9 and 10 stay at indices 1 and 3.
Example 2
- Input
nums = [7, 3, 20, 5, 18], limit = 1- Output
[7, 3, 20, 5, 18]- Why
- No two values differ by at most 1, so no swap is allowed.
Example 3
- Input
nums = [6, 1, 8, 3], limit = 3- Output
[1, 3, 6, 8]- Why
- Sorted, the values are 1, 3, 6, 8 with gaps 2, 3, 2, so all of them form one group and can be fully sorted.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^91 <= limit <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (union-find over all pairs) | O(n^2 + n log n) | O(n) |
| Optimal (sort, then split into gap groups) | O(n log n) | O(n) |
1Brute force (union-find over all pairs)
O(n^2 + n log n)All n^2 / 2 pairs are checked; sorting the groups adds n log n.O(n)The parent array and the grouped indices.Join every pair of indices whose values differ by at most limit. Each connected group of indices can be rearranged freely, so write its values back in sorted order onto its sorted indices.
- For every pair (i, j), if |nums[i] - nums[j]| <= limit, union i and j.
- Collect the indices of each component (they come out in increasing order).
- Sort the component's values and assign them to its indices in order.
class Solution {
private int[] parent;
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
int n = nums.length;
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (Math.abs(nums[i] - nums[j]) <= limit) parent[find(i)] = find(j);
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(find(i), k -> new ArrayList<>()).add(i);
int[] res = new int[n];
for (List<Integer> idx : groups.values()) {
List<Integer> vals = new ArrayList<>();
for (int i : idx) vals.add(nums[i]);
Collections.sort(vals);
for (int k = 0; k < idx.size(); k++) res[idx.get(k)] = vals.get(k);
}
return res;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
n = len(nums)
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for i in range(n):
for j in range(i + 1, n):
if abs(nums[i] - nums[j]) <= limit:
parent[find(i)] = find(j)
groups = {}
for i in range(n):
groups.setdefault(find(i), []).append(i)
res = [0] * n
for idx in groups.values():
vals = sorted(nums[i] for i in idx)
for k, i in enumerate(idx):
res[i] = vals[k]
return resclass Solution {
vector<int> parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
int n = nums.size();
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (abs(nums[i] - nums[j]) <= limit) parent[find(i)] = find(j);
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; i++) groups[find(i)].push_back(i);
vector<int> res(n);
for (auto& [root, idx] : groups) {
vector<int> vals;
for (int i : idx) vals.push_back(nums[i]);
sort(vals.begin(), vals.end());
for (size_t k = 0; k < idx.size(); k++) res[idx[k]] = vals[k];
}
return res;
}
};function lexicographicallySmallestArray(nums, limit) {
const n = nums.length;
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
if (Math.abs(nums[i] - nums[j]) <= limit) parent[find(i)] = find(j);
const groups = new Map();
for (let i = 0; i < n; i++) {
const r = find(i);
if (!groups.has(r)) groups.set(r, []);
groups.get(r).push(i);
}
const res = new Array(n);
for (const idx of groups.values()) {
const vals = idx.map((i) => nums[i]).sort((a, b) => a - b);
idx.forEach((i, k) => { res[i] = vals[k]; });
}
return res;
}2Optimal (sort, then split into gap groups)
O(n log n)One sort of all indices, plus sorting the runs, whose sizes add up to n.O(n)The sorted order, the result and a temporary index list.Sort the indices by value. Walking through the sorted order, a new group starts whenever the gap to the previous value is larger than limit, because no chain of swaps can cross that gap. Each group's values are already sorted; sort its indices and pair them up.
- order = indices sorted by nums value.
- Scan order and cut it into runs where consecutive values differ by at most limit.
- For each run [l, r): copy its indices, sort them, and set res[sortedIdx[k]] = nums[order[l + k]].
class Solution {
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
int n = nums.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(nums[a], nums[b]));
int[] res = new int[n];
int l = 0;
while (l < n) {
int r = l + 1;
while (r < n && nums[order[r]] - nums[order[r - 1]] <= limit) r++;
int[] idx = new int[r - l];
for (int k = l; k < r; k++) idx[k - l] = order[k];
Arrays.sort(idx);
for (int k = l; k < r; k++) res[idx[k - l]] = nums[order[k]];
l = r;
}
return res;
}
}class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
n = len(nums)
order = sorted(range(n), key=lambda i: nums[i])
res = [0] * n
l = 0
while l < n:
r = l + 1
while r < n and nums[order[r]] - nums[order[r - 1]] <= limit:
r += 1
idx = sorted(order[l:r])
for k in range(l, r):
res[idx[k - l]] = nums[order[k]]
l = r
return resclass Solution {
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
int n = nums.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return nums[a] < nums[b]; });
vector<int> res(n);
int l = 0;
while (l < n) {
int r = l + 1;
while (r < n && nums[order[r]] - nums[order[r - 1]] <= limit) r++;
vector<int> idx(order.begin() + l, order.begin() + r);
sort(idx.begin(), idx.end());
for (int k = l; k < r; k++) res[idx[k - l]] = nums[order[k]];
l = r;
}
return res;
}
};function lexicographicallySmallestArray(nums, limit) {
const n = nums.length;
const order = Array.from({ length: n }, (_, i) => i);
order.sort((a, b) => nums[a] - nums[b]);
const res = new Array(n);
let l = 0;
while (l < n) {
let r = l + 1;
while (r < n && nums[order[r]] - nums[order[r - 1]] <= limit) r++;
const idx = order.slice(l, r).sort((a, b) => a - b);
for (let k = l; k < r; k++) res[idx[k - l]] = nums[order[k]];
l = r;
}
return res;
}Edge cases to test
- A single element
- Two values that cannot be swapped directly but are linked through a middle value
- Duplicates (a difference of 0 is always within the limit)
- limit so large that the whole array can be sorted
Hints
Hint 1
Swaps chain: if a can swap with b and b with c, then a, b and c can be arranged in any order among their positions.
Hint 2
Sort the values. Two neighbours in sorted order belong to the same group exactly when their gap is at most limit.
Hint 3
Within one group, put the smallest value at the smallest index, the next one at the next index, and so on.
FAQ
What is the best time complexity for Make Lexicographically Smallest Array by Swapping Elements?
Optimal (sort, then split into gap groups) runs in O(n log n) time and O(n) extra space. One sort of all indices, plus sorting the runs, whose sizes add up to n.
Which pattern does Make Lexicographically Smallest Array by Swapping Elements use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Make Lexicographically Smallest Array by Swapping Elements?
Yes. Brute force (union-find over all pairs) takes O(n^2 + n log n) time and O(n) space. Join every pair of indices whose values differ by at most limit.
Which edge cases should I test for Make Lexicographically Smallest Array by Swapping Elements?
A single element; Two values that cannot be swapped directly but are linked through a middle value; Duplicates (a difference of 0 is always within the limit); limit so large that the whole array can be sorted.