<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 UnionFind:
    def __init__(self, n):
        self.count = n                             # number of disjoint sets
        self.parent = [i for i in range(n)]    # parent of given nodes
        self.rank = [1] * (n)                  # rank (aka size) of sub-tree
        self.mp = defaultdict(list)

    # find the root parent
    def find(self, n1):
        curr = n1

        # continue till you reach parent
        while curr != self.parent[curr]:
            self.parent[curr] = self.parent[self.parent[curr]]  # path compression
            curr = self.parent[curr]

        return curr

    # return False if cannot complete
    def union(self, n1, n2):

        # find parents for 2 nodes
        p1, p2 = self.find(n1), self.find(n2)

        # no union then
        if p1 == p2:
            return False

        # union by rank
        if self.rank[p2] > self.rank[p1]:
            self.parent[p1] = p2
            self.rank[p2] += self.rank[p1]
            heappush(self.mp[p2], n1)
        else:
            self.parent[p2] = p1
            self.rank[p1] += self.rank[p2]
            heappush(self.mp[p1], n2)

        # one more connection => one less disjoint
        

        return True

    # at the end we need to have one count to be fully connected
    def isConnected(self):
        return self.count == 1

    def get_min(self, a):
        pa = self.find(a)
        return heappop(self.mp[pa]) if self.mp[pa] else -1


class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
       
        # sort based on num value increasigly 
        paired = [(num, i) for i, num in enumerate(nums)]
        paired = sorted(paired)

        group = []     # each two adjacent number have difference less than the limit they sit in one group

        for num, i in paired:
        
            # add a new group if (1) empty group or (2) the 
            # difference with last element in the group is 
            # greater than limit
            if not group or num - group[-1][-1][0] > limit:
                group += [[]]

            # extend the existing last group
            group[-1] += [(num, i)]


        res = [0] * n
        for g in group:
            # already sorted
            nums = [num for num, _ in g]             

            # extract indices and sort them increasingly
            indices = [i for _, i in g]
            indices = sorted(indices)

            # put the num in the ordered list of indices
            for i, num in zip(indices, nums):
                res[i] = num

        return res

1163