2948. Make Lexicographically Smallest Array by Swapping Elements

trick, use group Sorting index

T: O(nlogn + n*nlogn), worst case
S: O(n)

```java
public class Solution {
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        List<Integer> indexes = new ArrayList<>();
        List<Integer> values = new ArrayList<>();
        TreeMap<Integer, List<Integer>> map = new TreeMap<>(); // value, list(index)
        for (int i = 0; i < nums.length; i++) {
            map.putIfAbsent(nums[i], new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        int[] result = new int[nums.length];
        Integer preKey = null;
        for (int key : map.keySet()) {
            if (preKey != null && key - preKey > limit) { // means new group, add to Result (with sort)
                addResult(result, indexes, values);
            }
            for (int index : map.get(key)) {
                // key - preKey <= limit, so keep adding to this group
                indexes.add(index);
                values.add(key);
            }

            preKey = key;
        }
        addResult(result, indexes, values);

        return result;
    }
    private void addResult(int[] result, List<Integer> indexes, List<Integer> values) {
        Collections.sort(indexes);
        for (int i = 0; i < indexes.size(); i++) {
            result[indexes.get(i)] = values.get(i);
        }
        indexes.clear();
        values.clear();
    }
}
/**
T: O(nlogn + n*nlogn), worst case
S: O(n)

grouping idea:
sort these values first, by TreeMap (values, index)
so values is sorted, so we can loop these sorted values to find cur_value - pre_value <= limit

-> case1: if fit cur_value - pre_value <= limit, means same group
case2: not fit -> means next group, a new group start


so now we continuously add (values, index) to this same group

ex:
index  0  1 2  3  4  5   6  7  8 9
      [1,60,34,84,62,56,39,76,49,38], limit = 4
sorted values:
index:0.  2   9   6     8   5   1   4.    7.   3
        |            |    |            |    |
      1,  34, 38, 39,  49,  56, 60, 62,  76 ,  84  

1 is a group,   34 - 1 > limit, so open new group (case2)
34, 38, 39 is a group, because 38 - 34 <= limit, 39 - 38 <= limit (case1)

34, 38, 39 real index is 2   9   6

so if we sort these index [2, 9, 6] to [2, 6, 9]
and put values with the index in values list
index list [2, 6, 9]
value list [34, 38, 39]
            
result become 
index  0  1 2  3  4  5  | 6         | 7  8   9.| 
      [1,60,34,84,62,56,| 39 becomes| 38,76,49,| 38 becomes 39] // like swap 30 to
        becomes:
       0. 1  2. 3. 4. 5. 6. 7. 8 9 
      [1,60,34,84,62,56,38,76,49,39]
       that's what we want!!
       
        5   1   4 -> sort
       56, 60, 62
       
       1  4. 5.  -> means these 3 to swap each other in different index 
       56 60 62.    because in question they said: we can swap any i, j in array
       so this idea is to group number together ( < limit), then swap them in index order
       but the number in this sort is still sorted number 
       (just index is different -> like after swaping                
       
       so
       [1,60,34,84,62,56,38,76,49,39]
       become
       [1,56,34,84,60,62,38,76,49,39] -> final ans , complete all group swap!

       so after all grouping and sort index:
       ans is:
      [1,56,34,84,60,62,38,76,49,39]




    x       x  x 
      x            x       x   
[1,60,34,84,62,56,39,76,49,38]

  |            |    |            |    |
1,  34, 38, 39,  49,  56, 60, 62, 76 ,  84 

[0]
[1]

[2]
[34]

[2, 9]
[34, 38]

[2, 9, 6]
[34, 38, 39]


[8]
[49]
[5]
[56]
[5, 1]
[56, 60]
[5, 1, 4]
[56, 60, 62]
[7]
[76]
[3]
[84]



 */

```

Better solution!

T: O(nlogn)
S: O(n)

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

        int groupId = 0;
        Map<Integer, Integer> numToGroup = new HashMap<>();
        numToGroup.put(sortedNum[0], groupId);
        Map<Integer, LinkedList<Integer>> groupToSortedNums = new HashMap<>();
        groupToSortedNums.computeIfAbsent(groupId, k -> new LinkedList<>()).add(sortedNum[0]);

        for (int i = 1; i < n; i++) {
            if (sortedNum[i] - sortedNum[i-1] > limit) {
                groupId++;
            }
            numToGroup.put(sortedNum[i], groupId);
            groupToSortedNums.computeIfAbsent(groupId, k -> new LinkedList<>()).add(sortedNum[i]);
        }

        int[] result = new int[n];
        for (int i = 0; i < n ; i++) {
            int origin = nums[i];
            int curGroupId = numToGroup.get(origin);
            LinkedList<Integer> sortedNums = groupToSortedNums.get(curGroupId);
            result[i] = sortedNums.pollFirst(); // ex: [34,45,47], poll 34
        }

        return result;
    }
}

/***



ex:
index  0  1 2  3  4  5   6  7  8 9
      [1,60,34,84,62,56,39,76,49,38], limit = 4

group index     0.       1.       2.     3.         4.   5
           |            |    |            |    |
sorted values:           
         1,  34, 38, 39,  49,  56, 60, 62,  76 ,  84  

sort nums
1,  34, 38, 39,  49,  56, 60, 62,  76 ,  84  

make:
numToGroup
1, 0
34,1
38,1
39,1...

groupToList (add to linkedList, and because we use sorted number, so here linkedList is sorted)
0 -> [1]
1 -> [34,38,39]
...

Rebuild the Array:
[1,60,34,84,62,56,39,76,49,38]
use original value to find group, then get smallest in group, then it's the new value for this index

Replace each number in the original array with the smallest available number from its group:

[1,60,34,84,62,56,39,76,49,38]
1 -> G0 -> [1], pop 1

60 -> G2 -> [56, 60, 62], pop 56 and replace 60...
34 -> G0 ->  [34, 38, 39], pop 34, still 34
 
final ans is:  [1,56,34,84,60,62,38,76,49,39]


T: O(nlogn)
S: O(n)
 */