# Make Lexicographically Smallest Array by Swapping Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements)
Canonical: https://scaleengineer.com/dsa/problems/make-lexicographically-smallest-array-by-swapping-elements
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## 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 <= 105`
* `1 <= nums[i] <= 109`
* `1 <= limit <= 109`

# Approaches
## Brute-force Graph Construction and Traversal
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.
**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).
**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.
### Explanation
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:
1.  **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`.
2.  **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.
3.  **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.
4.  **Return Result**: Once all components have been processed, the result array holds the lexicographically smallest possible array.

```java
// 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;
}
```
### 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.

## Optimized Grouping by Sorting
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.
**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.
**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.
### Explanation
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:
1.  **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.
2.  **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.
3.  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.
4.  **Return Result**: After all components are processed and their elements are placed in the result array, the array is returned.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums[i];
            pairs[i][1] = i;
        }

        // Step 1: Sort pairs based on values
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));

        int[] result = new int[n];
        int i = 0;
        while (i < n) {
            int j = i;
            // Step 2: Find the end of the current component
            while (j + 1 < n && (long)pairs[j + 1][0] - pairs[j][0] <= limit) {
                j++;
            }

            // We have a component from index i to j in the sorted pairs array
            List<Integer> componentValues = new ArrayList<>();
            List<Integer> componentIndices = new ArrayList<>();
            for (int k = i; k <= j; k++) {
                componentValues.add(pairs[k][0]);
                componentIndices.add(pairs[k][1]);
            }

            // Step 3: Sort original indices and place values
            Collections.sort(componentIndices);

            for (int k = 0; k < componentValues.size(); k++) {
                result[componentIndices.get(k)] = componentValues.get(k);
            }

            // Move to the next component
            i = j + 1;
        }

        return result;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> lexicographicallySmallestArray(vector<int> &nums, int limit) {
    int n = nums.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(),
         [&](int i, int j) { return nums[i] < nums[j]; });
    vector<int> ans(n);
    for (int i = 0; i < n;) {
      int j = i + 1;
      while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
        ++j;
      }
      vector<int> t(idx.begin() + i, idx.begin() + j);
      sort(t.begin(), t.end());
      for (int k = i; k < j; ++k) {
        ans[t[k - i]] = nums[idx[k]];
      }
      i = j;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```