Make Lexicographically Smallest Array by Swapping Elements
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as a graph problem. Each index of the array is treated as a node in a graph. An edge exists between two nodes (indices) i and j if their corresponding values nums[i] and nums[j] can be swapped, i.e., |nums[i] - nums[j]| <= limit. After building the graph, we find its connected components. All elements within a single connected component can be freely permuted among their original indices. To obtain the lexicographically smallest result, for each component, we sort the values and their original indices, then map the smallest values to the smallest indices.
Algorithm
- Create an adjacency list for a graph with
nnodes, wherenis the length ofnums. - Iterate through all pairs of indices
(i, j). If|nums[i] - nums[j]| <= limit, add an edge connecting nodesiandj. - Initialize a
visitedarray to track visited nodes and aresultarray to build the output. - Iterate through each index
ifrom0ton-1. Ifihas not been visited, start a graph traversal (like BFS or DFS) fromito find all indices belonging to the same connected component. - For each component found:
- Collect the values from
numscorresponding to the indices in the component. - Collect the indices themselves.
- Sort the list of values and the list of indices in ascending order.
- Populate the
resultarray by assigning the i-th sorted value to the position specified by the i-th sorted index.
- Collect the values from
- After processing all components, return the
resultarray.
Walkthrough
The fundamental idea is that the swap operation's reach is transitive. If element a can be swapped with b, and b with c, then a, b, and c are all mutually swappable among their original positions. This forms an equivalence relation, which partitions the array elements into groups. These groups correspond to the connected components of a graph.
The algorithm proceeds as follows:
- Build Graph: We construct an adjacency list for a graph with
nnodes (wherenis the length ofnums). We iterate through every possible pair of indices(i, j). If the absolute difference betweennums[i]andnums[j]is within thelimit, we add an edge between nodesiandj. - Find Connected Components: We use a boolean
visitedarray to keep track of processed nodes. We iterate from indexi = 0ton-1. Ifihasn't been visited, we initiate a graph traversal (e.g., Breadth-First Search or Depth-First Search) starting fromi. This traversal will discover all indices that belong to the same connected component. - Process Each Component: For each component discovered:
a. We gather all the values from
numsthat correspond to the indices in the current component. b. We also gather the indices themselves. c. To achieve the lexicographically smallest arrangement, we sort both the list of values and the list of indices in ascending order. d. Finally, we populate our result array by placing the k-th smallest value at the k-th smallest index from the component. - Return Result: Once all components have been processed, the result array holds the lexicographically smallest possible array.
// This is a conceptual illustration. A full implementation would be too verbose and likely time out.public int[] lexicographicallySmallestArray(int[] nums, int limit) { int n = nums.length; java.util.List<java.util.List<Integer>> adj = new java.util.ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new java.util.ArrayList<>()); } // Step 1: Build Graph (O(N^2)) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (Math.abs((long)nums[i] - nums[j]) <= limit) { adj.get(i).add(j); adj.get(j).add(i); } } } int[] result = new int[n]; boolean[] visited = new boolean[n]; // Step 2 & 3: Find and Process Components for (int i = 0; i < n; i++) { if (!visited[i]) { java.util.List<Integer> componentIndices = new java.util.ArrayList<>(); java.util.Queue<Integer> q = new java.util.LinkedList<>(); q.add(i); visited[i] = true; while(!q.isEmpty()){ int u = q.poll(); componentIndices.add(u); for(int v : adj.get(u)){ if(!visited[v]){ visited[v] = true; q.add(v); } } } java.util.List<Integer> componentValues = new java.util.ArrayList<>(); for (int index : componentIndices) { componentValues.add(nums[index]); } java.util.Collections.sort(componentIndices); java.util.Collections.sort(componentValues); for (int k = 0; k < componentIndices.size(); k++) { result[componentIndices.get(k)] = componentValues.get(k); } } } return result;}Complexity
Time
O(N^2). The dominant operation is building the graph, which involves checking all pairs of elements, taking O(N^2) time. The subsequent graph traversal and processing steps are also bounded by O(N^2).
Space
O(N^2). The adjacency list can store up to O(N^2) edges in the worst case (a fully connected graph).
Trade-offs
Pros
The approach is a direct and conceptually straightforward application of graph theory.
It correctly solves the problem for small input sizes.
Cons
Highly inefficient due to the O(N^2) complexity for graph construction.
Requires a large amount of memory for the adjacency list, up to O(N^2), which is not feasible for the given constraints.
This approach will result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for large inputs.
Solutions
Solution
class Solution {public int[] lexicographicallySmallestArray(int[] nums, int limit) { int n = nums.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; ++i) { 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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.