<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], k: int) -> List[int]:

        # n = len(nums)
        # for i in range(n):
        #     for j in range(i + 1, n):
        #         if nums[i] > nums[j] and -nums[j] + nums[i] <= limit:
        #             nums[i], nums[j] = nums[j], nums[i]
        # return nums
        # c = 0
        # n = len(nums)
        # d = [False] * n
        # left = float("inf")
        # right = -left
        # while c < n:
        #     l = []
        #     idx = []
        #     for i in range(n):
        #         print(left, right)
        #         if d[i]:
        #             continue
        #         if l == []:
        #             l.append(nums[i])
        #             idx.append(i)
        #             left = min(left, nums[i] - k)
        #             right = max(right, nums[i] + k)
        #             d[i] = True
        #             c += 1
        #         elif left <= nums[i] <= right:
        #             l.append(nums[i])
        #             idx.append(i)
        #             left = min(left, nums[i] - k)
        #             right = max(right, nums[i] + k)
        #             d[i] = True
        #             c += 1
        #     l.sort()
        #     print(l)
        #     for i in range(len(l)):
        #         nums[idx[i]] = l[i]
        # return nums
        n = len(nums)
        copy = [[nums[i], i] for i in range(n)]
        copy.sort()
        i = 0
        # print(copy)
        while i < n:
            left = copy[i][0] - k
            right = copy[i][0] + k
            j = i + 1
            idx = [copy[i][1]]
            while j < n and copy[j][0] <= right:
                idx.append(copy[j][1])
                # right = max(right, )
                right = copy[j][0] + k
                j += 1
            # should check if j is out of bound or condition failed
            # print(i, j, idx)
            idx.sort()
            for it in range(len(idx)):
                nums[idx[it]] = copy[i][0]
                i += 1
        return nums
            
1044