<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>

import math
class Solution:
    class Group:
        def __init__(self, n, ind, limit):
            self.nums = [n]
            self.ind = [ind]
            self.ub = n+limit
            self.lb = n-limit
            self.limit = limit
        
        def add(self, n, i):
            self.nums.append(n)
            self.ind.append(i)
            self.ub = max(self.ub, n+self.limit)
            self.lb = min(self.lb, n-self.limit)
        
        def addAll(self, group):
            self.nums.extend(group.nums)
            self.ind.extend(group.ind)
            self.ub = max(self.ub, group.ub)
            self.lb = min(self.lb, group.lb)

        def canAdd(self, n):
            return self.lb<=n<=self.ub
        
        def sort(self):
            self.nums.sort()
            self.ind.sort()
        
    class GroupManager:
        def __init__(self, limit):
            self.groups = []
            self.limit = limit
        
        def merge_groups(self, groups, n, i):
            "Assuming we are getting only mergable groups in this function"
            ng = Solution.Group(n, i, self.limit)
            for g in groups:
                ng.addAll(g)
                self.remove_group(g)
            
            self.add_group(ng)

        def add_group(self, group):
            self.groups.append(group)
        
        def remove_group(self, group):
            self.groups.remove(group)

    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:        
        np = [(n, i) for i, n in enumerate(nums)]
        np = sorted(np, key=lambda v: v[0])
        groups = [[np[0]]]
        for i in range(1, len(np)):
            if np[i][0]-limit<=np[i-1][0]:
                groups[len(groups)-1].append(np[i])
            else:
                groups.append([np[i]])
        
        for g in groups:
            indexes = []
            for ele in g:
                indexes.append(ele[1])
            
            indexes.sort()
            for i , n in zip(indexes, g):
                nums[i] = n[0]
    
        return nums


1007