Make Lexicographically Smallest Array by Swapping Elements solution and explanation
IBM
Google
9 more videos on this problem
Make Lexicographically Smallest Array by Swapping Elements - Leetcode 2948 - PythonNeetCodeIO · 17:40 · 14K views
Make Lexicographically Smallest Array by Swapping Elements | Brute Force | Optimal | Leetcode 2948codestorywithMIK · 59:07 · 11K views
Make Lexicographically Smallest Array by Swapping Elements | Leetcode 2948Techdose · 23:14 · 7K views
2948. Make Lexicographically Smallest Array by Swapping Elements | SortingAryan Mittal · 19:03 · 3K views
2948. Make Lexicographically Smallest Array by Swapping Elements | Weekly Leetcode 373codingMohan · 20:45 · 2K views
2948. Make Lexicographically Smallest Array by Swapping Elements (Leetcode Medium)Programming Live with Larry · 13:23 · 645 views
Daily Leetcode #1761: Jan 25, 2025 - 2948. Make Lexicographically Smallest Array by Swapping...Programming Live with Larry · 27:07 · 541 views
Leetcode 2948. Make Lexicographically Smallest Array by Swapping ElementsElite Code · 32:48 · 232 views
Make Lexicographically Smallest Array by Swapping Elements - LeetCode 2948 - PythonAlpha-Code · 22:01 · 227 views
2948. Make Lexicographically Smallest Array by Swapping Elements | Leetcode Daily ChallengeEthos Typos · 18:21 · 193 views
The problem
You are given a 0-indexed array of positive integers nums and a positive integer limit.
In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit.
Return the lexicographically smallest array that can be obtained by performing the operation any number of times.
An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.
Example 1:
Input: nums = [1,5,3,9,8], limit = 2 Output: [1,3,5,8,9] Explanation: Apply the operation 2 times: - Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8] - Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9] We cannot obtain a lexicographically smaller array by applying any more operations. Note that it may be possible to get the same result by doing different operations.
Example 2:
Input: nums = [1,7,6,18,2,1], limit = 3 Output: [1,6,7,18,1,2] Explanation: Apply the operation 3 times: - Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1] - Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1] - Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2] We cannot obtain a lexicographically smaller array by applying any more operations.
Example 3:
Input: nums = [1,7,28,19,10], limit = 3 Output: [1,7,28,19,10] Explanation: [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= limit <= 109
Approach overview
Problem Overview: You are given an array nums and a limit value. You may swap two elements if their absolute difference is ≤ limit. The goal is to perform any number of valid swaps so the final array is lexicographically smallest.
Approach 1: Greedy Swap with Value Grouping (O(n log n) time, O(n) space)
The key observation: if two numbers can swap directly or through a chain of swaps, they belong to the same connected group. Sort pairs (value, index) by value, then scan and group elements where adjacent value differences are ≤ limit. Inside each group, the values can be freely rearranged. Collect the indices from that group, sort the indices, and place the smallest values into the smallest positions to minimize lexicographic order. This approach uses sorting and greedy placement to build the smallest possible prefix at every step.
Approach 2: Union-Find Component Construction (O(n log n) time, O(n) space)
You can model the swap rule as a graph where indices are connected if their values differ by ≤ limit. After sorting values, union adjacent elements that satisfy the constraint using Union Find. Each connected component represents indices that can freely swap. For each component, gather its indices and values, sort both lists, and assign the smallest values to the smallest indices. This formalizes the connectivity idea and works well when thinking about transitive swaps.
Approach 3: Segment Tree Optimization (O(n log n) time, O(n) space)
When handling large arrays or frequent queries about valid placements, a segment tree can track available indices while assigning values. After grouping values that can interact, store free positions in a tree structure and repeatedly place the smallest value into the leftmost available valid index. The tree supports fast updates and queries in O(log n). This approach combines array manipulation with ordered placement for efficient large-scale operations.
Recommended for interviews: The greedy grouping solution is the expected answer. It shows you recognize that the swap rule creates connected components and that sorting values inside each component minimizes lexicographic order. Explaining the union-find interpretation demonstrates deeper algorithmic understanding, but the greedy sorted grouping approach is simpler to implement during an interview.
Approach 1: Greedy Swap Approach
This approach utilizes a greedy method by iterating over the array and attempting to swap elements to their lexicographically smallest possible positions while respecting the limit constraint.
For each element in the array, find the smallest valid element that can be swapped to its position, keeping the |nums[i] - nums[j]| <= limit condition in mind. This is done through nested iteration for simplicity, but careful attention to the limit ensures efficiency.
The process is repeated for each element until no further swaps yield a smaller lexicographic order.
def makeSmallest(nums, limit):
n = len(nums)
for i in range(n):
smallest_index = i
for j in range(i + 1, n):
if abs(nums[i] - nums[j]) <= limit and nums[j] < nums[smallest_index]:
smallest_index = j
if smallest_index != i:
nums[i], nums[smallest_index] = nums[smallest_index], nums[i]
return nums
# Example usage
print(makeSmallest([1, 5, 3, 9, 8], 2))function makeSmallest(nums, limit) {
for (let i = 0; i < nums.length; i++) {
let smallestIndex = i;
for (let j = i + 1; j < nums.length; j++) {
if (Math.abs(nums[i] - nums[j]) <= limit && nums[j] < nums[smallestIndex]) {
smallestIndex = j;
}
}
if (smallestIndex !== i) {
[nums[i], nums[smallestIndex]] = [nums[smallestIndex], nums[i]];
}
}
return nums;
}
// Example usage
console.log(makeSmallest([1, 5, 3, 9, 8], 2));The function makeSmallest iterates over each element and finds the smallest possible element that it can be swapped with under the limit constraint. If a more optimal position is found, a swap is performed.
Time Complexity: O(n^2), where n is the number of elements in nums, due to nested iteration.
Space Complexity: O(1), as the solution modifies the array in place.
Approach 2: Segment Tree Optimization
In this approach, a Segment Tree is used for query optimization. It allows us to efficiently determine the smallest possible element within a specific range that can swap places under the limit constraint.
As the array is processed, the Segment Tree helps find the minimal element in constant time after preprocessing, making the swapping process more efficient compared to a naive approach.
A priority queue could be used instead of a segment tree for similar effect while sometimes offering simpler implementations.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> makeSmallest(vector<int>& nums, int limit) {
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
int smallest = i;
for (int j = i + 1; j < n; ++j) {
if (abs(nums[i] - nums[j]) <= limit && nums[j] < nums[smallest]) {
smallest = j;
}
}
if (smallest != i) {
swap(nums[i], nums[smallest]);
}
}
return nums;
}
int main() {
vector<int> nums = {1, 5, 3, 9, 8};
int limit = 2;
nums = makeSmallest(nums, limit);
for (int num : nums) {
cout << num << " ";
}
return 0;
}using System;
using System.Linq;
class Program {
static void Main() {
int[] nums = { 1, 5, 3, 9, 8 };
int limit = 2;
nums = MakeSmallest(nums, limit);
Console.WriteLine(string.Join(" ", nums));
}
static int[] MakeSmallest(int[] nums, int limit) {
int n = nums.Length;
for (int i = 0; i < n; i++) {
int smallest = i;
for (int j = i + 1; j < n; j++) {
if (Math.Abs(nums[i] - nums[j]) <= limit && nums[j] < nums[smallest]) {
smallest = j;
}
}
if (smallest != i) {
int temp = nums[i];
nums[i] = nums[smallest];
nums[smallest] = temp;
}
}
return nums;
}
}This C++ solution uses a repetitive greedy selection for swapping to achieve a lexicographically smaller array. It iteratively swaps the current element with the smallest eligible element found under the limit constraint.
Time Complexity: O(n^2), due to the pair-wise swaps performed across the array.
Space Complexity: O(1), since we're modifying the array directly without additional space usage.
Approach 3: Sorting
According to the problem description, the sorted array nums can be partitioned into several subarrays such that the difference between adjacent elements in each subarray does not exceed limit.
The lexicographically smallest array obtainable through swapping is thus the one where the elements within each subarray are sorted and placed back into their original positions in order.
We first pair each element in nums with its index to form an array of tuples, then sort by element value. We then traverse the sorted tuple array, identify the range of each subarray, sort the elements within each subarray by their original indices, and fill them back into the corresponding positions to obtain the final result.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array nums.
class Solution {
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
int n = nums.length;
Integer[] idx = new Integer[n];
Arrays.setAll(idx, i -> i);
Arrays.sort(idx, (i, j) -> nums[i] - nums[j]);
int[] ans = new int[n];
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
++j;
}
Integer[] t = Arrays.copyOfRange(idx, i, j);
Arrays.sort(t, (x, y) -> x - y);
for (int k = i; k < j; ++k) {
ans[t[k - i]] = nums[idx[k]];
}
i = j;
}
return ans;
}
}function lexicographicallySmallestArray(nums: number[], limit: number): number[] {
const n: number = nums.length;
const idx: number[] = Array.from({ length: n }, (_, i) => i);
idx.sort((i, j) => nums[i] - nums[j]);
const ans: number[] = Array(n).fill(0);
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
j++;
}
const t: number[] = idx.slice(i, j).sort((a, b) => a - b);
for (let k: number = i; k < j; k++) {
ans[t[k - i]] = nums[idx[k]];
}
i = j;
}
return ans;
}func lexicographicallySmallestArray(nums []int, limit int) []int {
n := len(nums)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
slices.SortFunc(idx, func(i, j int) int { return nums[i] - nums[j] })
ans := make([]int, n)
for i := 0; i < n; {
j := i + 1
for j < n && nums[idx[j]]-nums[idx[j-1]] <= limit {
j++
}
t := slices.Clone(idx[i:j])
slices.Sort(t)
for k := i; k < j; k++ {
ans[t[k-i]] = nums[idx[k]]
}
i = j
}
return ans
}impl Solution {
pub fn lexicographically_smallest_array(nums: Vec<i32>, limit: i32) -> Vec<i32> {
let n = nums.len();
let mut idx: Vec<usize> = (0..n).collect();
idx.sort_by_key(|&i| nums[i]);
let mut ans = vec![0; n];
let mut i = 0;
while i < n {
let mut j = i + 1;
while j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit {
j += 1;
}
let mut t = idx[i..j].to_vec();
t.sort();
for k in i..j {
ans[t[k - i]] = nums[idx[k]];
}
i = j;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Swap Approach | Time Complexity: O(n^2), where n is the number of elements in nums, due to nested iteration. |
| Segment Tree Optimization | Time Complexity: O(n^2), due to the pair-wise swaps performed across the array. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Swap with Value Grouping | O(n log n) | O(n) | Best general solution. Simple implementation using sorting and grouping. |
| Union-Find Components | O(n log n) | O(n) | Useful when modeling swaps as connectivity problems or when practicing union-find patterns. |
| Segment Tree Optimization | O(n log n) | O(n) | Helpful for large inputs or when efficient index allocation queries are needed. |
Frequently asked questions
Is Make Lexicographically Smallest Array by Swapping Elements easy or hard?
The problem is rated Medium. The challenge is recognizing that swap rules create connected components of values. Once that insight is clear, sorting and greedy reassignment make the implementation straightforward.
Make Lexicographically Smallest Array by Swapping Elements Python/Java solution
In Python or Java, the standard solution sorts (value, index) pairs, groups elements whose value difference is ≤ limit, and then assigns sorted values to sorted indices within each group. The implementation uses arrays, sorting, and simple grouping logic with O(n log n) complexity.
How to solve Make Lexicographically Smallest Array by Swapping Elements in O(n)?
An exact O(n) solution is not practical because identifying swappable ranges requires sorting by value. The best achievable complexity is O(n log n). Sorting enables grouping elements whose value differences are within the allowed limit and then rearranging them greedily.
What is the best approach for Make Lexicographically Smallest Array by Swapping Elements?
The most practical approach is greedy grouping after sorting the values. Sort pairs of (value, index), group elements whose value difference is ≤ limit, then assign the smallest values to the smallest indices inside each group. This produces the lexicographically smallest array in O(n log n) time and O(n) space.
Is Make Lexicographically Smallest Array by Swapping Elements asked at Google/Amazon/Meta?
Problems involving lexicographic minimization, swap constraints, and connected components appear frequently in interviews at companies like Google, Amazon, and Meta. Variations often combine sorting with union-find or greedy grouping strategies.
What data structure is used in Make Lexicographically Smallest Array by Swapping Elements?
Common structures include arrays, sorting utilities, and union-find (disjoint set). Union-find helps detect connected components formed by valid swaps, while sorting organizes values so components can be identified efficiently.
What is the time complexity of Make Lexicographically Smallest Array by Swapping Elements?
The optimal solution runs in O(n log n) time because the array must be sorted to detect swappable value groups. After sorting, grouping and reassigning values is linear. Space complexity is O(n) for storing indices and grouped values.