Make Lexicographically Smallest Array by Swapping Elements

Make Lexicographically Smallest Array by Swapping Elements

What is this problem about?

In this problem, you are given an integer array and a limit. You are allowed to swap any two elements in the array if and only if their absolute difference is less than or equal to the limit. You can perform this swap any number of times. Your objective is to return the lexicographically smallest array possible.

Why is this asked in interviews?

This is an excellent problem to evaluate a candidate's understanding of Connected Components. Interviewers ask it to see if you realize that the swapping rule implies transitivity: if you can swap A with B, and B with C, you can effectively swap A and C! This transforms a seemingly impossible string of permutations into a structured grouping problem.

Algorithmic pattern used

This problem relies on Sorting and Union Find / Grouping. Because of the transitive property of swapping, elements that can be swapped form connected components or "groups".

1. Sort a copy of the array alongside their original indices.
2. Iterate through the sorted array. If the difference between adjacent sorted elements is $\le$ limit, they belong to the same group.
3. For each group, extract their original indices, sort those indices, and then place the sorted group values into those sorted index slots in the final answer array.

Example explanation

Array: [1, 5, 3, 9, 8], limit = 2.

1. Pair with indices: [(1,0), (5,1), (3,2), (9,3), (8,4)].
2. Sort by value: [(1,0), (3,2), (5,1), (8,4), (9,3)].
3. Group them checking adjacent diffs $\le 2$:
   • 1 and 3: Diff is 2. Group 1.
   • 3 and 5: Diff is 2. Group 1.
   • 5 and 8: Diff is 3. Break! 8 starts Group 2.
   • 8 and 9: Diff is 1. Group 2.
4. Process Group 1 values [1, 3, 5]. Their original indices were [0, 2, 1]. Sort indices: [0, 1, 2].
   • Place 1 at idx 0, 3 at idx 1, 5 at idx 2.
5. Process Group 2 values [8, 9]. Original indices [4, 3]. Sort indices: [3, 4].
   • Place 8 at idx 3, 9 at idx 4. Final Array: [1, 3, 5, 8, 9].

Common mistakes candidates make

A very common mistake is attempting to simulate the swaps using BFS or standard array manipulation, which is impossibly slow ($O(N^2)$ or worse). Another mistake is using a full Union-Find data structure to group elements based on the unsorted array, checking every pair, which results in $O(N^2)$ checks. You must sort the array first so you only need to check adjacent elements to build the groups.

Interview preparation tip

When tackling the Make Lexicographically Smallest Array coding problem, recognize the "Swapping Transitivity" rule. Whenever a problem allows unlimited swaps under a connectivity constraint, you are essentially just sorting independent sub-arrays. Group the values, group their original indices, sort both, and weave them back together.