I start my approach by pairing each element with its original index and sorting these pairs based on their values. Next, I form groups of elements where each consecutive pair in the sorted list has a difference within the given limit. These groups represent sets of elements that can be swapped with each other through a chain of allowed operations. For example, if elements A, B, and C are sorted and consecutive in value, and |A-B| ≤ limit and |B-C| ≤ limit, they form a single group even if |A-C| exceeds the limit indirectly.
For each group, I extract the original indices of its elements and sort these indices. I then assign the sorted values of the group to these sorted indices.
class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
n = len(nums)
sorted_pairs = sorted([(nums[i], i) for i in range(n)], key=lambda x: x[0])
groups = []
if not sorted_pairs:
return []
current_group = [sorted_pairs[0]]
for i in range(1, n):
if sorted_pairs[i][0] - sorted_pairs[i-1][0] <= limit:
current_group.append(sorted_pairs[i])
else:
groups.append(current_group)
current_group = [sorted_pairs[i]]
groups.append(current_group)
result = [0] * n
for group in groups:
indices = [pair[1] for pair in group]
sorted_indices = sorted(indices)
values = [pair[0] for pair in group]
for i in range(len(sorted_indices)):
result[sorted_indices[i]] = values[i]
return result- Time: O(nlogn)
- Space: O(n)
