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

'''
Having multiple swaps doesn't matter because this problem isn't based on indices

Brute Force - Iterate from each index and swap if it's smaller -> O(n^2) -> bubble sort with a condition

Greedy - First number should be the smallest so swap with the smallest number possible

The problem with the freqs is that you ask yourself at each index - is there anything smaller than this -> easy yes or no question but then what if you had swapped this number so it doesn't exist - you don't know what number is in that index anymore...

What if I assume at each index -> if this number exists then it can be swapped for something less, otherwise if it does not exist, it must have been swapped for something that is greater than it cause it was preferred in the prior indices. If it was swapped for something greater, must have been within the limit.

5 1 -> swap 1 5, 

Pseudocode
- Have of a frequency of each number in the array
- Go through each index and see for each number at that index, what's the smallest neighbor and swap it, removing the frequency of that neighbor

After looking at solution
- Grouping idea, if you have 20 15 10 5 1 and limit == 5, you realize that you can get the 1 to the front by first getting 15 to the front, then get the 10 to the front, then get 5 to the front and then 1
- What this tells you is that there is some sort of grouping that can be involved which is that if you have numbers that are <= limit in a non-descending order then they can be put into any order that is possible

Pseudocode
- Sort nums, keeping track of its indices
- Need to group each numbers that are within k distance of the previous number
- I go through each number in the original nums
    - Ask myself what parent does this number belong to (need parents[num] not parents[idx]) and pop the smallest number from that group
'''
from collections import deque
class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        parents = {}
        for i, num in enumerate(nums):
            if num not in parents:
                parents[num] = i
                
        sorted_nums = sorted([[num, i] for i, num in enumerate(nums)])
        
        for i in range(1, len(sorted_nums)):
            num, idx = sorted_nums[i]
            prev_num, prev_idx = sorted_nums[i - 1]
            
            if num - prev_num <= limit:
                parents[num] = parents[prev_num]
        
        groups = defaultdict(deque)
     
        for num, _ in sorted_nums:
            parent = parents[num]
            groups[parent].append(num)
            
        res = []
        
        for num in nums:
            parent = parents[num]
            res.append(groups[parent].popleft())
            
        return res
        
1141