We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make Lexicographically Smallest Array by Swapping Elements

Difficulty: Medium

Problem Description

You are given a 0-indexed array of positive integers nums and a positive integer limit. In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit. Return the lexicographically smallest array that can be obtained by performing the operation any number of times.

Key Insights

  • Swapping elements is limited by the difference defined by limit.
  • Elements that can be swapped together form connected components based on their values.
  • Each connected component can be sorted independently to achieve the lexicographically smallest order.
  • The result is the combination of individual sorted components.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting of connected components. Space Complexity: O(n) - for storing the indices of connected components.

Solution

To solve the problem, we can use the Union-Find (Disjoint Set Union) data structure to group indices of nums that can be swapped together based on the defined limit. After identifying the connected components, we sort each component and replace the original indices with the sorted values. This ensures the smallest possible arrangement for each component, leading to the overall lexicographically smallest array.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def makeSmallestArray(nums, limit):
    n = len(nums)
    uf = UnionFind(n)
    
    # Create unions based on the limit
    for i in range(n):
        for j in range(i + 1, n):
            if abs(nums[i] - nums[j]) <= limit:
                uf.union(i, j)
    
    # Group indices by their root parent
    from collections import defaultdict
    components = defaultdict(list)
    for i in range(n):
        root = uf.find(i)
        components[root].append(i)
    
    # Create the result array
    result = [0] * n
    for indices in components.values():
        # Extract the values and sort them
        values = [nums[i] for i in indices]
        values.sort()
        # Place sorted values back into their indices
        for idx, value in zip(sorted(indices), values):
            result[idx] = value
            
    return result
← Back to All Questions