2948. Make Lexicographically Smallest Array by Swapping Elements
Difficulty: Medium | Published on 2026-08-29
Let's teach this one from absolute zero too, following the same structure.
1. Problem in Very Simple Language
You have a list of positive numbers, INLINECODE0, and a number called INLINECODE1.
You are allowed to swap any two numbers in the list, but only if the difference between them (ignoring sign) is INLINECODE2 or less. You can do this swap as many times as you want, on any pair of positions, as long as each individual swap obeys that rule.
Your job: figure out the smallest possible arrangement of the list you can reach, where "smallest" means: compare position by position (like comparing words in a dictionary, but with numbers) — the first list that has a smaller number at the first position where the two lists differ, wins.
What's given: the array INLINECODE3, and the max allowed difference INLINECODE4. What to find: the arrangement of these same numbers that is lexicographically smallest, reachable using only swaps of numbers that differ by at most INLINECODE5. What to return: that rearranged array.
2. Real-Life Analogy
Imagine a row of people standing in line, each holding a card with a number on it (their height, say). Two people are allowed to swap their cards only if their heights are close enough — within INLINECODE6 of each other. But here's the key trick: if person A can swap with person B, and person B can swap with person C, then even though A and C might be too far apart to swap directly, cards can still "travel" from A to C by hopping through B. So really, we should think of people as being sorted into friend groups — everyone in a group can (indirectly) trade cards with everyone else in that same group, no matter how many hops it takes, as long as each hop individually satisfies the INLINECODE7 rule.
Once we know the friend groups, within each group we can freely rearrange cards among the positions that belong to that group, so we should hand out the smallest cards to the earliest (leftmost) positions in each group to make the whole line look as small as possible from left to right.
3. Important Programming Concepts I Need First
Array
Concept: A numbered list of values, positions starting at 0. Example: INLINECODE8 — position 0 has INLINECODE9, position 4 has INLINECODE10. Why we need it: The entire input and output are arrays.Sorting
Concept: Arranging values from smallest to largest. Example: INLINECODE11 sorted becomes INLINECODE12. Why we need it: We'll want to look at numbers in increasing order to figure out which ones are "close enough" to chain together.Graph
Concept: A collection of "things" (called nodes) with "connections" (called edges) between some pairs of them. Not necessarily roads on a map — it can be any relationship. Example: If numbers INLINECODE13 and INLINECODE14 are close enough to swap, draw a connecting line between them. That's an edge in a graph where each number is a node. Why we need it: We can think of each number as a node, and "these two numbers can be swapped" as an edge. Numbers that are connected (even indirectly, through other numbers) form one big cluster.Connected Components (a graph concept)
Concept: If you group all nodes that can reach each other (directly or through a chain of connections) into clusters, each cluster is called a "connected component." Example: If INLINECODE15 are connected and INLINECODE16 are connected, then INLINECODE17 are all in the same component, even though INLINECODE18 and INLINECODE19 might not be directly connected. Why we need it: This is exactly our "friend group" idea from the analogy — all numbers in one connected component can be freely rearranged among each other's original positions.HashMap
Concept: A structure that lets you store and instantly look up a value using a "key" (like looking up a word's meaning using the word itself, instead of reading a whole dictionary page by page). Example: INLINECODE20 Why we need it: After finding which group each number belongs to, we need to quickly gather "all the numbers in group 5" together.Sorting (again, applied to indices too)
We'll also need to remember where (which positions) each number in a group originally came from, then place the sorted numbers back into those sorted positions.Union-Find (Disjoint Set Union) — a new, important concept
Concept: A clever data structure specifically built to answer "are these two things in the same group?" and "merge these two groups into one" extremely fast, without needing to actually build and search a full graph every time. Simple Example: Think of it like a bunch of small friend circles that can merge into bigger friend circles. Each person starts in their own circle. When you learn INLINECODE21 and INLINECODE22 are friends, you merge their circles into one. Later, you can instantly ask "are INLINECODE23 and INLINECODE24 in the same circle?" even if their connection required many merges. Why we need it for this problem: After sorting INLINECODE25, we check each pair of neighboring sorted values — if they're within INLINECODE26, they belong in the same group. Union-Find lets us build these groups very efficiently as we scan through.Time Complexity
We'll need this to explain why our final solution is fast enough for up to 100,000 numbers.4. Understand the Input
Take Example 1: CODEBLOCK0
INLINECODE27 is our starting arrangement of 5 numbers, at positions 0 through 4: position 0 = INLINECODE28, position 1 = INLINECODE29, position 2 = INLINECODE30, position 3 = INLINECODE31, position 4 = INLINECODE32. INLINECODE33 means: we're only allowed to directly swap two numbers if their difference is 2 or less. We are looking for: the smallest possible final arrangement, using any sequence of allowed swaps. Why does it matter that INLINECODE34 and INLINECODE35 are 2 apart? Because INLINECODE36, so a direct swap between wherever INLINECODE37 and INLINECODE38 sit is legal. Similarly INLINECODE39 and INLINECODE40 differ by INLINECODE41, so they can swap too.5. Understand the Output
Output: INLINECODE42
This is the smallest number placed first, then the next smallest, and so on — it's actually just the fully sorted version of the array! Why is this achievable? Because as the explanation shows, INLINECODE43 are all within INLINECODE44 of their neighbors when sorted (INLINECODE45, INLINECODE46), so they form one big connected group — meaning we can rearrange all three of them freely among their three original positions (0, 1, 2). Likewise INLINECODE47 and INLINECODE48 differ by INLINECODE49, forming their own group, freely rearrangeable among positions 3 and 4. Since each group can be freely sorted internally, and putting the smallest value first within each group is always best for lexicographic order, we sort each group and place the values back into the group's positions in increasing order.6. Solve the Example Manually
Let's solve Example 1 by hand.
Step 1: Sort the numbers to see which ones are \"close\" to each other. Sorted: INLINECODE50
Step 2: Walk through the sorted list, checking each pair of neighbors — are they within INLINECODE51?
| Pair | Difference | ≤ limit (2)? | Same group? |
|---|---|---|---|
| 1, 3 | 2 | Yes | Group together |
| 3, 5 | 2 | Yes | Group together |
| 5, 8 | 3 | No | New group starts |
| 8, 9 | 1 | Yes | Group together |
Step 3: Figure out which original positions each group's numbers came from.
Original array: INLINECODE54 at positions INLINECODE55.
Value INLINECODE56 was at position 0. Value INLINECODE57 was at position 1. Value INLINECODE58 was at position 2. Value INLINECODE59 was at position 3. Value INLINECODE60 was at position 4.
Group INLINECODE61 occupies positions INLINECODE62. Group INLINECODE63 occupies positions INLINECODE64.
Step 4: Within each group, sort the positions AND sort the values, then match smallest value to smallest position.
Group INLINECODE65: positions sorted = INLINECODE66, values sorted = INLINECODE67. Assign: position 0 → 1, position 1 → 3, position 2 → 5.
Group INLINECODE68: positions sorted = INLINECODE69, values sorted = INLINECODE70. Assign: position 3 → 8, position 4 → 9.
Step 5: Build the final array from these assignments.
| Position | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 1 | 3 | 5 | 8 | 9 |
7. Think Like a Programmer
What do I know? Which pairs of numbers are directly swappable (difference ≤ limit). What do I need to find? The smallest possible rearrangement. What can I try? If I try to reason about individual swaps one at a time, I'll get lost — there could be thousands of possible swap sequences. I need a bigger-picture idea. What happens if I try every possibility? Way too slow — with up to 100,000 numbers, trying different swap sequences directly is hopeless. Can I make it faster? Yes — realize that swapping is like a \"connection\" between two numbers, and connections chain together transitively (if A can reach B and B can reach C, then A's card can eventually end up where C was, via a chain of legal swaps). This screams \"connected components.\" What information should I remember? For each number, which group (component) it belongs to, and which original positions belong to that group. What pattern do I notice? Numbers that are close in value (within INLINECODE72 of their neighbor, once sorted) end up chained into the same group. This means sorting first makes it very easy to spot the groups — you just walk through the sorted list and start a new group whenever the gap to the previous number exceeds INLINECODE73. What should happen at each step? Within each group, assign the smallest available value to the smallest available position, since that greedily minimizes the array from left to right — and it's always safe to do, because within a group, ALL rearrangements are achievable (we can freely permute).
8. Start With the Brute Force Solution
Brute force idea: Try to simulate the swapping process directly — repeatedly scan for any swappable pair that would improve the lexicographic order, perform it, and repeat until no more improving swaps exist.
Why it's tempting: It directly mimics \"do the operation any number of times,\" which is literally what the problem describes.
Why it's a bad idea in practice: There's no obvious, cheap way to know which swap to do next without deeply understanding the structure — and repeatedly scanning all pairs for a swappable, improving pair takes INLINECODE74 per pass, and might need many passes. With INLINECODE75 up to 100,000, INLINECODE76 is 10 billion — far too slow.
Time complexity: Roughly INLINECODE77 or worse per full attempt, and it's not even guaranteed to be simple to implement correctly (how do you know when you're truly done, or that a locally-improving swap doesn't block a better global rearrangement?).
Space complexity: INLINECODE78 for the array itself.
Since actually writing \"keep swapping while it helps\" correctly is tricky and slow, let's skip straight past this shaky brute force and go directly to reasoning about structure (Section 7's insight), which is really the natural next step for this problem. (Unlike Two Sum-style problems, here the \"obvious\" brute force isn't even clearly correct without a lot of extra care — so the real lesson is: recognize the connected-components structure early.)
9. Why Is a Naive Simulation Not Ideal?
Imagine 100,000 people in a line, and you're trying to figure out the best swap to do next by comparing every pair of people to every other pair, over and over, until nobody wants to swap anymore. Even a single full scan of all pairs is about 10 billion comparisons — your computer would take way too long. We need an approach that figures out the entire answer using just a small number of passes over the data, not repeated pairwise scanning.
11. Find the Better Approach
"Can we avoid doing unnecessary work?"
Yes — instead of thinking swap-by-swap, think group-by-group.
CODEBLOCK1
⭐ Key Insight
Before the insight
We were thinking about this as a sequence of individual swap actions, trying to decide \"what should I swap right now?\"The problem
Individual swaps are hard to reason about directly, and there are too many of them to try.The insight
\"Can swap\" is a transitive relationship (if A can trade with B, and B can trade with C, then eventually A's value can end up wherever C was, and vice versa, via intermediate swaps) — so all numbers reachable from each other through a chain of legal swaps form one interchangeable group. Within a group, any rearrangement of that group's values among that group's original positions is achievable. And once we know that, the best (lexicographically smallest) thing to do within a group is obvious: put the smallest values at the earliest positions.After the insight
The whole problem reduces to: (1) find these groups (connected components), (2) for each group, sort its values and sort its positions, and (3) match them up smallest-to-smallest. No simulation of individual swaps needed at all — and finding the groups is fast if we first sort the numbers, because then two numbers can only possibly be \"linked\" if they're within INLINECODE79, and if we scan the sorted list, consecutive elements within INLINECODE80 of each other are guaranteed to be linkable directly, and this chains naturally into full groups.13. Dry Run the Optimized Solution
Let's dry run Example 2 this time, to see a case with more moving parts.
CODEBLOCK2
Step 1: Pair each value with its original index, then sort by value.
Original (value, index) pairs: INLINECODE81
Sorted by value: INLINECODE82
Step 2: Scan through sorted values, grouping consecutive ones that differ by ≤ limit (3).
| Compare | Values | Difference | ≤ 3? | Same group? |
|---|---|---|---|---|
| (1,0) vs (1,5) | 1, 1 | 0 | Yes | same group |
| (1,5) vs (2,4) | 1, 2 | 1 | Yes | same group |
| (2,4) vs (6,2) | 2, 6 | 4 | No | new group |
| (6,2) vs (7,1) | 6, 7 | 1 | Yes | same group |
| (7,1) vs (18,3) | 7, 18 | 11 | No | new group |
Step 3: Within each group, sort by original index, and match to sorted values in order.
Group A: indices INLINECODE86 (sorted), values INLINECODE87 (already sorted) → position 0 gets 1, position 4 gets 1, position 5 gets 2.
Group B: indices INLINECODE88 (sorted), values INLINECODE89 (already sorted) → position 1 gets 6, position 2 gets 7.
Group C: index INLINECODE90, value INLINECODE91 → position 3 gets 18.
Step 4: Assemble the final array.
| Position | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Value | 1 | 6 | 7 | 18 | 1 | 2 |
14. Optimized Code
CODEBLOCK3
CODEBLOCK4
15. Explain Optimized Code Line by Line
INLINECODE93 — these two arrays are the core of Union-Find. INLINECODE94 tells you \"who is index INLINECODE95 currently pointing to as its group leader.\" INLINECODE96 is a rough measure of how \"tall\" a group's tree structure is, used just to keep things efficient. INLINECODE97 — at the very start, every index is its own separate group (pointing to itself). INLINECODE98 — we bundle each value together with its original position, because after sorting by value, we still need to remember where it came from. INLINECODE99 — sort these pairs purely by value (ascending), keeping the original index attached to each. The INLINECODE100 loop with INLINECODE101 — this is where we build our groups. We check every consecutive pair in the sorted-by-value list; if their values are close enough (INLINECODE102), we merge their original indices into the same Union-Find group. We only need to check consecutive pairs because if a chain exists at all, it will show up as a sequence of consecutive \"close enough\" jumps once sorted. INLINECODE103 — this function walks up the \"parent\" pointers until it finds an index that points to itself (the group's leader / root), and path compression (INLINECODE104) flattens the structure as we go, making future lookups faster. INLINECODE105 — finds each side's group leader; if they're already the same, nothing to do. Otherwise, it attaches one group under the other, using INLINECODE106 to decide which one becomes the new leader (keeping the overall structure shallow, so INLINECODE107 stays fast). INLINECODE108 — after all unions are done, we go through every index INLINECODE109, ask \"who's your group leader (root)?\", and collect all indices sharing the same leader into one list. This effectively rebuilds our \"friend groups\" from the analogy. Inside the INLINECODE110 loop: INLINECODE111 — sort the positions in this group in increasing order (so we know which position is \"first,\" \"second,\" etc., within the group). We gather all the actual INLINECODE112 values that live at those positions, into a list called INLINECODE113, then sort that list too. INLINECODE114 — this is the final matching step: the smallest position in the group gets the smallest value, the second-smallest position gets the second-smallest value, and so on. Finally, we return INLINECODE115, the completed answer array.
16. Test With Multiple Examples
Example 1 — Normal Case
INLINECODE116 → dry-ran manually in Section 6 → Output: INLINECODE117 ✔️Example 2 — Different Case
INLINECODE118 → dry-ran in Section 13 → Output: INLINECODE119 ✔️Example 3 — Edge Case (no operations possible at all)
INLINECODE120. Sort: INLINECODE121. Check consecutive gaps: INLINECODE122 (no), INLINECODE123 (yes! within limit), INLINECODE124 (no), INLINECODE125 (no). So INLINECODE126 and INLINECODE127 actually do form a small group together — but wait, in the original array they're at positions: value INLINECODE128 is at index 1, value INLINECODE129 is at index 4. Group INLINECODE130: sorted indices INLINECODE131, sorted values INLINECODE132 → position 1 gets 7 (unchanged), position 4 gets 10 (unchanged)! Since the group happens to already have its smallest value at its smallest position, nothing visibly changes. All other values are alone in their own groups (no legal swap partner), so they also stay put. Final output: INLINECODE133 — unchanged ✔️, matching the expected output, and showing why even a \"matched\" group can result in no visible change if it was already optimally arranged.17. Edge Cases
Array has only one element → trivially, it's already the smallest possible arrangement (no swaps needed or possible). No two numbers are within INLINECODE134 of each other → every number is its own group of size 1 → output equals input, unchanged. All numbers are within INLINECODE135 of each other (one giant group) → the entire array becomes fully sorted, just like a normal sort. Duplicate values → they'll always be within INLINECODE136 (difference INLINECODE137), so duplicates always end up in the same group as each other (and often pull in more neighbors too). Very large values close to the max (INLINECODE138) — since we only ever compute differences between actual array values (never adding unrelated large numbers together in a way that could overflow), we're safe using regular INLINECODE139 subtraction here in Java, as both values fit well within int range and the difference does too.18. Time Complexity
What is time complexity? It estimates how the total amount of work grows as your input grows — like estimating that alphabetizing a bigger stack of files takes proportionally longer, using a general rule of thumb rather than a stopwatch.
CODEBLOCK5
Why: The dominant cost is sorting — both the initial sort of all values, and later, all the little per-group sorts (which together touch each element only a constant number of times, but still cost a log factor). Union-Find itself is famously close to INLINECODE140 per operation on average (technically INLINECODE141, an extremely slowly-growing function you can safely think of as \"basically constant\"). Compare this to brute-force INLINECODE142 simulation: for INLINECODE143, INLINECODE144 is about 1.7 million operations, while INLINECODE145 would be 10,000,000,000 — a massive, practically-infinite difference in real time.
19. Space Complexity
INLINECODE146 and INLINECODE147 arrays: size INLINECODE148 each. The INLINECODE149 array: size INLINECODE150 (each holding 2 numbers). The INLINECODE151 map and its lists: together hold every index exactly once, so INLINECODE152 total. The INLINECODE153 array: size INLINECODE154.
Overall extra space: INLINECODE155.
20. Common Mistakes Beginners Make
❌ \"I should check every pair of numbers in the array to see if they're within INLINECODE156, and connect them directly.\" ✅ You only need to check consecutive pairs after sorting — if a longer chain exists, it will always show up as a sequence of consecutive close-enough jumps in the sorted order, so checking neighbors is enough and much faster.
❌ \"Since I can only directly swap numbers within INLINECODE157, only directly swappable pairs can end up trading places.\" ✅ Swaps can chain — if INLINECODE158 can swap with INLINECODE159, and INLINECODE160 can swap with INLINECODE161, then INLINECODE162's value can eventually reach where INLINECODE163 was (through a sequence of swaps), even if INLINECODE164 and INLINECODE165 themselves are too far apart to swap directly.
❌ \"I should sort the whole array and just return that.\" ✅ Full sorting is only correct when everything forms one giant group. If some values are too far apart to ever connect (directly or indirectly), those values must stay confined to their own original group's positions — sorting everything blindly would be an illegal rearrangement.
❌ \"I'll assign the smallest position to whatever value happens to come first.\" ✅ You must sort both the group's positions and the group's values independently, then match them up smallest-to-smallest — this greedy matching is what actually produces the lexicographically smallest result.
21. How to Recognize This Pattern in Other Problems
Watch for these signal phrases:
CODEBLOCK6
Whenever swapping/merging is allowed transitively (through chains, not just direct pairs) and you need to find what's ultimately interchangeable, think Union-Find / connected components.
22. Interview Thinking
CODEBLOCK7
Applied here: sorting first exposes the chain structure cheaply, Union-Find captures \"who's ultimately interchangeable with whom,\" and the final greedy match (smallest value ↔ smallest position, per group) finishes the job.
23. Mini Challenge
Try these before checking the answers:
1. If INLINECODE166 and INLINECODE167, which pairs (by value) are directly within INLINECODE168 of each other? Are all three numbers in one group, or split into groups? 2. Once you know the groups from Question 1, and you know which original positions each group's numbers came from, what's the final rule for assigning values back to positions? 3. Why do we only need to compare consecutive elements in the sorted array to build all the groups, instead of comparing every pair?
Answer to Mini Challenge
1. Sorted: INLINECODE169. INLINECODE170 (connected), INLINECODE171 (connected). So all three end up in one single group (2 connects to 4, 4 connects to 6, so 2 and 6 are indirectly linked too, even though INLINECODE172 directly). 2. Sort the group's original positions, sort the group's values, then assign the smallest value to the smallest position, the second-smallest value to the second-smallest position, and so on. 3. Because if two values are far apart in sorted order with nothing \"in between\" close enough, checking non-consecutive pairs can never reveal a connection that consecutive-pair-checking would miss — any indirect chain between two far-apart values must physically pass through the values sitted between them once sorted, so scanning neighbor-to-neighbor is guaranteed to catch every real connection.
24. Final Revision
🧠 Problem in One Sentence
Group numbers that can be transitively swapped (chain of differences ≤ limit), then within each group place the smallest values at the smallest original positions.🔑 Main Idea
\"Can swap\" is transitive, so this is a connected-components problem — solve it with sorting + Union-Find, then greedily match sorted values to sorted positions within each group.⚙️ Algorithm
1. Pair each value with its original index; sort these pairs by value. 2. Union consecutive pairs (by value) whenever their difference is ≤ limit. 3. Group all original indices by their final Union-Find root. 4. For each group: sort its positions, sort its values, assign smallest value → smallest position, and so on. 5. Return the assembled result array.⏱️ Complexity
Time: INLINECODE173 Space: INLINECODE174🎯 Pattern to Remember
Transitive \"can-connect\" relationship + \"make it smallest\" → sort + Union-Find (connected components) + greedy match within each group.25. Beginner Quiz
1. (Understanding) Why can two numbers end up swappable even if their direct difference is bigger than INLINECODE175? 2. (Basic concept) What does a \"connected component\" mean in your own words, using this problem as the example? 3. (Logic) Why is it enough to check only consecutive elements in the sorted array when building groups, instead of checking all pairs? 4. (Dry run) For INLINECODE176, sort the values, identify the groups, and figure out the final answer array. 5. (Complexity/pattern) Why is the final time complexity INLINECODE177 rather than INLINECODE178, and what key phrase in a problem statement should make you think \"Union-Find / connected components\" in the future?
Take your time — send me your answers whenever you're ready, and I'll walk through them with you!