Make Lexicographically Smallest Array by Swapping Elements

Med

#2628Time: 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).2 companies

Algorithms

Sorting Union Find

Data structures

Array

Companies

Atlassian PhonePe

Prompt

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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= limit <= 10⁹

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 n nodes, where n is the length of nums.
Iterate through all pairs of indices (i, j). If |nums[i] - nums[j]| <= limit, add an edge connecting nodes i and j.
Initialize a visited array to track visited nodes and a result array to build the output.
Iterate through each index i from 0 to n-1. If i has not been visited, start a graph traversal (like BFS or DFS) from i to find all indices belonging to the same connected component.
For each component found:
- Collect the values from nums corresponding 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 result array by assigning the i-th sorted value to the position specified by the i-th sorted index.
After processing all components, return the result array.

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 n nodes (where n is the length of nums). We iterate through every possible pair of indices (i, j). If the absolute difference between nums[i] and nums[j] is within the limit, we add an edge between nodes i and j.
Find Connected Components: We use a boolean visited array to keep track of processed nodes. We iterate from index i = 0 to n-1. If i hasn't been visited, we initiate a graph traversal (e.g., Breadth-First Search or Depth-First Search) starting from i. 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 nums that 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.

1// This is a conceptual illustration. A full implementation would be too verbose and likely time out.2public int[] lexicographicallySmallestArray(int[] nums, int limit) {3    int n = nums.length;4    java.util.List<java.util.List<Integer>> adj = new java.util.ArrayList<>();5    for (int i = 0; i < n; i++) {6        adj.add(new java.util.ArrayList<>());7    }8 9    // Step 1: Build Graph (O(N^2))10    for (int i = 0; i < n; i++) {11        for (int j = i + 1; j < n; j++) {12            if (Math.abs((long)nums[i] - nums[j]) <= limit) {13                adj.get(i).add(j);14                adj.get(j).add(i);15            }16        }17    }18 19    int[] result = new int[n];20    boolean[] visited = new boolean[n];21 22    // Step 2 & 3: Find and Process Components23    for (int i = 0; i < n; i++) {24        if (!visited[i]) {25            java.util.List<Integer> componentIndices = new java.util.ArrayList<>();26            java.util.Queue<Integer> q = new java.util.LinkedList<>();27            28            q.add(i);29            visited[i] = true;30            31            while(!q.isEmpty()){32                int u = q.poll();33                componentIndices.add(u);34                for(int v : adj.get(u)){35                    if(!visited[v]){36                        visited[v] = true;37                        q.add(v);38                    }39                }40            }41 42            java.util.List<Integer> componentValues = new java.util.ArrayList<>();43            for (int index : componentIndices) {44                componentValues.add(nums[index]);45            }46 47            java.util.Collections.sort(componentIndices);48            java.util.Collections.sort(componentValues);49 50            for (int k = 0; k < componentIndices.size(); k++) {51                result[componentIndices.get(k)] = componentValues.get(k);52            }53        }54    }55    return result;56}

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.

This approach significantly optimizes the process of finding swappable groups by avoiding the O(N^2) pair-wise comparisons. The key insight is that if we sort the numbers, any two numbers that can be swapped will either be adjacent or connected through a chain of adjacent swappable numbers in the sorted list. This is because if a < b < c and |c - a| <= limit, it must follow that |b - a| <= limit and |c - b| <= limit. Therefore, we only need to check adjacent elements in a sorted version of the array to determine the groups, which can be done much more efficiently.

Algorithm

Create an array of pairs, where each pair consists of an element from nums and its original index: (nums[i], i).
Sort this array of pairs based on the element values in ascending order.
Iterate through the sorted pairs to identify components. A component is a contiguous block of pairs where the value difference between any two adjacent pairs is less than or equal to limit.
For each identified component:
- Extract the values and the original indices into separate lists.
- The list of values will already be sorted due to the initial sort.
- Sort the list of original indices.
- Place the sorted values into a result array at the positions specified by the sorted indices.
Return the fully constructed result array.

Walkthrough

The core idea is that sorting the elements allows us to identify the connected components (groups of swappable elements) in linear time after an initial O(N log N) sort.

The algorithm is as follows:

Pair and Sort: First, we associate each number with its original index by creating pairs of (value, original_index). We then sort this list of pairs based on the values.
Group and Process: We iterate through the sorted pairs and group them into components. A new component begins whenever the difference between the current element's value and the previous element's value exceeds the limit. A component is thus a contiguous block in the sorted list of pairs.
For each component: a. We collect the values and original indices from the pairs in the current block. b. The list of values is inherently sorted because we are iterating through the already sorted pairs. c. We sort the list of original indices to determine the earliest positions the group's elements can occupy. d. We then assign the sorted values to the sorted indices in the final result array. This ensures that smaller values from the group are placed at smaller indices, which is the requirement for a lexicographically smallest array.
Return Result: After all components are processed and their elements are placed in the result array, the array is returned.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.Collections;4import java.util.List;5 6class Solution {7    public int[] lexicographicallySmallestArray(int[] nums, int limit) {8        int n = nums.length;9        int[][] pairs = new int[n][2];10        for (int i = 0; i < n; i++) {11            pairs[i][0] = nums[i];12            pairs[i][1] = i;13        }14 15        // Step 1: Sort pairs based on values16        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));17 18        int[] result = new int[n];19        int i = 0;20        while (i < n) {21            int j = i;22            // Step 2: Find the end of the current component23            while (j + 1 < n && (long)pairs[j + 1][0] - pairs[j][0] <= limit) {24                j++;25            }26 27            // We have a component from index i to j in the sorted pairs array28            List<Integer> componentValues = new ArrayList<>();29            List<Integer> componentIndices = new ArrayList<>();30            for (int k = i; k <= j; k++) {31                componentValues.add(pairs[k][0]);32                componentIndices.add(pairs[k][1]);33            }34 35            // Step 3: Sort original indices and place values36            Collections.sort(componentIndices);37 38            for (int k = 0; k < componentValues.size(); k++) {39                result[componentIndices.get(k)] = componentValues.get(k);40            }41 42            // Move to the next component43            i = j + 1;44        }45 46        return result;47    }48}

Complexity

Time

O(N log N). The initial sorting of pairs dominates the time complexity, taking O(N log N). The subsequent linear scan to find components takes O(N). Sorting indices within each component has a total complexity of `sum(s_i log s_i)` over all components `i` of size `s_i`, which is bounded by O(N log N).

Space

O(N). We need O(N) space for the `pairs` array. The temporary lists for `componentValues` and `componentIndices` can also take up to O(N) space in the worst-case scenario where all elements form a single component.

Trade-offs

Pros

Highly efficient with an O(N log N) time complexity, which is optimal for a sorting-based problem.
Well-suited for the given constraints of the problem.
The implementation is relatively straightforward and avoids the complexity of explicit graph data structures.

Cons

Requires O(N) extra space to store the pairs and the data for each component.

Solutions

Solution

1class Solution {2public3  int[] lexicographicallySmallestArray(int[] nums, int limit) {4    int n = nums.length;5    Integer[] idx = new Integer[n];6    for (int i = 0; i < n; ++i) {7      idx[i] = i;8    }9    Arrays.sort(idx, (i, j)->nums[i] - nums[j]);10    int[] ans = new int[n];11    for (int i = 0; i < n;) {12      int j = i + 1;13      while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {14        ++j;15      }16      Integer[] t = Arrays.copyOfRange(idx, i, j);17      Arrays.sort(t, (x, y)->x - y);18      for (int k = i; k < j; ++k) {19        ans[t[k - i]] = nums[idx[k]];20      }21      i = j;22    }23    return ans;24  }25}

1class Solution {2public:3  vector<int> lexicographicallySmallestArray(vector<int> &nums, int limit) {4    int n = nums.size();5    vector<int> idx(n);6    iota(idx.begin(), idx.end(), 0);7    sort(idx.begin(), idx.end(),8         [&](int i, int j) { return nums[i] < nums[j]; });9    vector<int> ans(n);10    for (int i = 0; i < n;) {11      int j = i + 1;12      while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {13        ++j;14      }15      vector<int> t(idx.begin() + i, idx.begin() + j);16      sort(t.begin(), t.end());17      for (int k = i; k < j; ++k) {18        ans[t[k - i]] = nums[idx[k]];19      }20      i = j;21    }22    return ans;23  }24};

1class Solution:2    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]: n = len(nums) arr = sorted(zip(nums, range(n))) ans = [0] * n i = 0 while i < n: j = i + 1 while j < n and arr[j][0] - arr[j - 1][0] <= limit: j += 1 idx = sorted(k for _, k in arr[i: j]) for k, (x, _) in zip(idx, arr[i: j]): ans[k] = x 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.

← Previous

Previous problem

Next problem