LeetCode Solutions Blog

Make Lexicographically Smallest Array by Swapping Elements

Number: 3219

Difficulty: Medium

Paid? No

Problem Description

Given a 0-indexed array of positive integers nums and a positive integer limit, you can swap any two numbers nums[i] and nums[j] if |nums[i] - nums[j]| <= limit. The goal is to perform any number of operations to obtain the lexicographically smallest array possible.

Key Insights

The swap condition can be modeled as an edge connecting two indices if the absolute difference of their corresponding values is ≤ limit.
Indices connected through a sequence of such valid swaps form a connected component, meaning elements within that component can be arbitrarily rearranged.
To obtain the lexicographically smallest outcome, for each connected component, sort the indices (positions) and the corresponding values separately; then reassign the smallest available value to the smallest index.
Instead of checking every pair (which is O(n²)), note that sorting the array by value and performing union on adjacent pairs (when the gap between consecutive values is ≤ limit) efficiently builds the connected components.

Space and Time Complexity

Time Complexity: O(n log n) – due to sorting the array and the per-component sorting. Space Complexity: O(n) – for union-find structure and auxiliary storage for grouping indices.

Solution

We solve the problem by using a union-find (disjoint-set) data structure. The key steps are:

Pair each element with its index.
Sort these pairs by the element value.
Iterate through the sorted pairs and union adjacent indices when their value difference is ≤ limit. This efficiently groups indices that can swap indirectly.
For each connected component, collect its indices, sort them, and also sort their corresponding numbers.
Place the sorted numbers into the array at the sorted indices to ensure the lexicographically smallest arrangement.
Return the resulting array.

Code Solutions

# Python Code Solution

# Union Find class implementation
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size  # for union by rank

    def find(self, x):
        # Path compression heuristic
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Union by rank heuristic
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def makeSmallestArray(nums, limit):
    n = len(nums)
    
    # Initialize union-find structure for indices.
    uf = UnionFind(n)
    
    # Create pairs of (num, index) and sort them by num.
    num_index_pairs = [(num, i) for i, num in enumerate(nums)]
    num_index_pairs.sort(key=lambda x: x[0])
    
    # Union adjacent pairs in sorted order if their difference <= limit.
    for k in range(1, n):
        if abs(num_index_pairs[k][0] - num_index_pairs[k-1][0]) <= limit:
            uf.union(num_index_pairs[k][1], num_index_pairs[k-1][1])
    
    # Group indices by their root parent.
    components = {}
    for i in range(n):
        root = uf.find(i)
        if root not in components:
            components[root] = []
        components[root].append(i)
    
    # Prepare a result array.
    result = [0] * n
    
    # For each component, sort the indices and the corresponding values.
    for comp_indices in components.values():
        comp_indices.sort()  # sort indices in ascending order
        # Extract values from the original nums at these indices
        comp_values = [nums[i] for i in comp_indices]
        comp_values.sort()  # sort values to have the smallest at the smallest index
        for idx, value in zip(comp_indices, comp_values):
            result[idx] = value

    return result

# Example usage:
# nums = [1,5,3,9,8], limit = 2
# Expected output: [1,3,5,8,9]
print(makeSmallestArray([1,5,3,9,8], 2))