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

def merge(nums,idx_arr,start,mid,end):
    #print(start,mid,end,end - start + 1)
    #print(idx_arr,nums)
    temp = [0 for i in range(end - start + 1)]
    temp_idx = [0 for i in range(end - start + 1)]
    k=0
    p1,p2 = start,mid+1
    while(p1<=mid and p2<=end):
        if nums[p1]<nums[p2]:
            temp[k]=nums[p1]
            temp_idx[k] = idx_arr[p1]
            k+=1
            p1+=1
        else:
            temp[k]=nums[p2]
            temp_idx[k] = idx_arr[p2]
            k+=1
            p2+=1
    while(p1<=mid):
        temp[k]=nums[p1]
        temp_idx[k] = idx_arr[p1]
        k+=1
        p1+=1
    while(p2<=end):
        temp[k]=nums[p2]
        temp_idx[k] = idx_arr[p2]
        k+=1
        p2+=1
    #print("abc",temp_idx,k,start)
    for i in range(k):
        nums[i+start] = temp[i]
        idx_arr[i+start] = temp_idx[i]
    #print(idx_arr,"bca")


def mergeSort(nums,idx_arr,start,end):
    if start==end:
        return
    mid = (start + end) // 2
    mergeSort(nums,idx_arr,start,mid)
    mergeSort(nums,idx_arr,mid+1,end)
    merge(nums,idx_arr,start,mid,end)

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        idx_arr = [i for i in range(len(nums))]
        mergeSort(nums,idx_arr,0,len(nums)-1)
        dit = {}
        dit[nums[0]]=[[nums[0],idx_arr[0]]]
        parent= nums[0]
        for i in range(len(nums)-1):
            if i+1<len(nums) and nums[i+1]-nums[i] <= limit :
                dit[parent].append([nums[i+1],idx_arr[i+1]])
            else:
                dit[nums[i+1]]=[[nums[i+1],idx_arr[i+1]]]
                parent= nums[i+1]
        #print(dit)
        ans = [0 for i in range(len(nums))]
        for i in dit:
            lis = sorted(dit[i], key=lambda x: x[1])
            lis1=dit[i]

            for z in range(len(lis)):
                ans[lis[z][1]]=lis1[z][0]
        return ans
        

        
48087