<p>You are given a <strong>0-indexed</strong> array of <strong>positive</strong> integers <code>nums</code> and a <strong>positive</strong> integer <code>limit</code>.</p>

<p>In one operation, you can choose any two indices <code>i</code> and <code>j</code> and swap <code>nums[i]</code> and <code>nums[j]</code> <strong>if</strong> <code>|nums[i] - nums[j]| &lt;= limit</code>.</p>

<p>Return <em>the <strong>lexicographically smallest array</strong> that can be obtained by performing the operation any number of times</em>.</p>

<p>An array <code>a</code> is lexicographically smaller than an array <code>b</code> if in the first position where <code>a</code> and <code>b</code> differ, array <code>a</code> has an element that is less than the corresponding element in <code>b</code>. For example, the array <code>[2,10,3]</code> is lexicographically smaller than the array <code>[10,2,3]</code> because they differ at index <code>0</code> and <code>2 &lt; 10</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,3,9,8], limit = 2
<strong>Output:</strong> [1,3,5,8,9]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,7,6,18,2,1], limit = 3
<strong>Output:</strong> [1,6,7,18,1,2]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,7,28,19,10], limit = 3
<strong>Output:</strong> [1,7,28,19,10]
<strong>Explanation:</strong> [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= limit &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        '''
        union find. 
        if |nums[i] - nums[j]| <= limit and |nums[j] - nums[k]| <= limit, then we can sort nums[i], nums[j], nums[k] and put them in i, j, k position
        1. get unique nums
        2. sort the uniqe nums
        3. union: the connection by checking i - pre_i <= limit
        4. find: the parent for each value
        5. sort index and value for each group with same parent
        '''
        parent = { v:  v for v in nums }
        rank = { v: 0 for v in parent }
        
        def find(i):
            if parent[i] == i:
                return parent[i]
            else:
                parent[i] = find(parent[i])
                return parent[i]

        def union(i, j):
            pi = find(i)
            pj = find(j)
            if rank[pi] > rank[pj]:
                parent[pj] = pi
            elif rank[pj] < rank[pi]:
                parent[pi] = p[j]
            else:
                parent[pj] = pi
                rank[pi] += 1
        j = None
        for i in sorted(parent):
            if j and i - j <= limit:
                union(i, j)
            j = i
        ret = [0] * len(nums)
        group_by_parent = {}
        for i, v in enumerate(nums):
            pi = find(v)
            if pi not in group_by_parent:
                group_by_parent[pi] = []
            group_by_parent[pi].append((v, i))
        #print(group_by_parent)
        
        for p in group_by_parent:
            sorted_index = sorted([i for _, i in group_by_parent[p]])
            sorted_value = sorted([v for v, _ in group_by_parent[p]])

            for i, v in zip(sorted_index, sorted_value):
                ret[i] = v
        
        return ret

66212