Make Lexicographically Smallest Array by Swapping Elements
Asked at Uber
Problem
Given an array nums and a limit, you can swap any two elements if their absolute difference is at most limit. Find the lexicographically smallest array achievable after performing any number of swaps.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | MEDIUM | View all Uber questions → |
How to Think About It
Brute force: try all permutations reachable by swaps, but this is factorial time.
Two elements can be swapped if their difference is at most limit, forming connected groups.
Sort the array and use union-find to group elements that can reach each other.
For each group, place the smallest available element at the smallest available index.
Optimal: sort indices by value, union adjacent indices whose values differ by at most limit, then assign sorted values to sorted indices within each group.
Optimal Approach
Create a sorted copy of the array. Use union-find to group indices whose values differ by at most limit when considered in sorted order. For each group of connected indices, assign the smallest available sorted values to the smallest indices in the group. This guarantees the lexicographically smallest arrangement because within each group, elements are freely interchangeable and we place the smallest values at the earliest positions. Time complexity is O(n log n) for sorting plus O(n alpha(n)) for union-find.
What Trips People Up in Real Interviews
Clarify that the limit applies to the absolute difference of values, not indices.
Recognize this as a connectivity problem where elements in the same group are interchangeable.
Explain why sorting values within each group and placing them at the smallest indices gives the lexicographically smallest result.
Discuss the union-find approach for grouping elements efficiently.
Mention edge cases like all elements being in one group or no swaps being possible.
Solution Code
class Solution:
def lexicographicallySmallestArray(self, nums: list[int], limit: int) -> list[int]:
n = len(nums)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px != py:
parent[px] = py
sorted_indices = sorted(range(n), key=lambda i: nums[i])
for i in range(1, n):
if nums[sorted_indices[i]] - nums[sorted_indices[i - 1]] <= limit:
union(sorted_indices[i], sorted_indices[i - 1])
groups = {}
for i in range(n):
root = find(i)
if root not in groups:
groups[root] = []
groups[root].append(i)
result = [0] * n
for indices in groups.values():
sorted_vals = sorted(nums[i] for i in indices)
sorted_pos = sorted(indices)
for pos, val in zip(sorted_pos, sorted_vals):
result[pos] = val
return resultFrequently Asked Questions
What is the Make Lexicographically Smallest Array by Swapping Elements problem?
Given an array nums and a limit, you can swap any two elements if their absolute difference is at most limit. Find the lexicographically smallest array achievable after performing any number of swaps.
How do you solve Make Lexicographically Smallest Array by Swapping Elements?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Make Lexicographically Smallest Array by Swapping Elements?
Make Lexicographically Smallest Array by Swapping Elements is asked at Uber. It is a medium difficulty problem.
What are common mistakes on Make Lexicographically Smallest Array by Swapping Elements?
- Clarify that the limit applies to the absolute difference of values, not indices.
- Recognize this as a connectivity problem where elements in the same group are interchangeable.
- Explain why sorting values within each group and placing them at the smallest indices gives the lexicographically smallest result.
- Discuss the union-find approach for grouping elements efficiently.
- Mention edge cases like all elements being in one group or no swaps being possible.