MediumArrayUnion FindSortingUpdated Sep 2026

2948. Make Lexicographically Smallest Array by Swapping Elements

Asked at Uber, Goldman Sachs

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

2

Problem

You get an array nums of positive integers and a number limit. In one move you may pick two indices i and j and swap nums[i] with nums[j], but only if the two values differ by at most limit (that is, |nums[i] - nums[j]| <= limit).

You may repeat this move as many times as you like. Return the lexicographically smallest array you can reach. An array a is lexicographically smaller than b if at the first index where they differ, a has the smaller value.

The key idea: two values can be swapped directly only when they are close. But swaps chain together, so a value can travel through a series of close values. Values that are connected this way can be rearranged freely among their positions.

Which values can trade places

nums1539801234orange pair differs by 2, blue pair differs by 1 —both are swappabletarget1358901234put the smaller value of each pair first to get thesmallest array
With limit = 2, the values 3 and 5 are linked, and 8 and 9 are linked, so each pair can be reordered.

Constraints

  • ●1 <= nums.length <= 10^5
  • ●1 <= nums[i] <= 10^9
  • ●1 <= limit <= 10^9

Examples

Example 1
Inputnums = [1,5,3,9,8], limit = 2
Output[1,3,5,8,9]
Why5 and 3 differ by 2, so we swap them to get [1,3,5,9,8]. Then 9 and 8 differ by 1, so we swap them to get [1,3,5,8,9]. The values 3 and 5 can trade places, and 8 and 9 can trade places, so each pair ends up in increasing order.
Example 2
Inputnums = [1,7,6,18,2,1], limit = 3
Output[1,6,7,18,1,2]
WhyThe values 1, 2, 6 and 7 are all linked by small gaps, so they can move around freely. The value 18 is far from everything, so it stays at index 3. We put the smallest values at the earliest positions: 1, 6, 7 before index 3, then 1, 2 after it.
Example 3
Inputnums = [1,7,28,19,10], limit = 3
Output[1,7,28,19,10]
WhyNo two values differ by 3 or less, so no swap is allowed at all. The array stays exactly as it is.

Asked At

2 companies
CompanyDifficulty
UberMediumView all Uber questions →
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Brute force: try all permutations reachable by swaps, but this is factorial time.

2

Two elements can be swapped if their difference is at most limit, forming connected groups.

3

Sort the array and use union-find to group elements that can reach each other.

4

For each group, place the smallest available element at the smallest available index.

5

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.

Group by sorted neighbours

sorted valuesgap 2gap 11358901234Step 1 — sort the values and join neighbours whose gapis <= limitgroupsvaluesidx 0idx 1-2idx 3-413589Step 2 — each group holds values that can be placedanywhere inside its own index setresult1358901234Step 3 — write each group's sorted values into itssorted positionssort values, union neighbours with gap <= limiteach group: sorted values -> sorted indices
Sort the values, link neighbours that are close enough, then refill each group's positions with its values in sorted order.
ComplexityTime O(n log n)Space O(n)Sorting the indices costs O(n log n); the union-find grouping is nearly linear, so sorting dominates.

What Trips People Up in Real Interviews

1

Clarify that the limit applies to the absolute difference of values, not indices.

2

Recognize this as a connectivity problem where elements in the same group are interchangeable.

3

Explain why sorting values within each group and placing them at the smallest indices gives the lexicographically smallest result.

4

Discuss the union-find approach for grouping elements efficiently.

5

Mention edge cases like all elements being in one group or no swaps being possible.

Solution Code

O(n log n) time
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 result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Make Lexicographically Smallest Array by Swapping Elements?

Make Lexicographically Smallest Array by Swapping Elements is asked at Uber, Goldman Sachs. 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.