LeetCode 2948 - Make Lexicographically Smallest Array by Swapping Elements

The problem asks us to transform a given array of positive integers nums into its lexicographically smallest form by performing a specific swap operation any number of times.

leetcodemediumarrayunion-findsorting

LeetCode Problem 2948

Difficulty: 🟡 Medium
Topics: Array, Union-Find, Sorting

Solution

Problem Understanding

The problem asks us to transform a given array of positive integers nums into its lexicographically smallest form by performing a specific swap operation any number of times. The operation allows swapping any two elements nums[i] and nums[j] only if the absolute difference between them is at most limit. The lexicographically smallest array is one where, comparing elements from left to right, the first element that differs from another array is smaller.

The input nums is a list of up to 10^5 integers, each up to 10^9. The limit also can be very large. This indicates that brute force methods that repeatedly swap every valid pair are infeasible due to time constraints. We need a solution that identifies which elements can ultimately be swapped among themselves efficiently.

Edge cases include arrays where no swaps are possible (all differences exceed limit), arrays where all elements are equal, or very small arrays of length 1. These cases will test that the algorithm correctly respects the limit condition and handles small input sizes.

Approaches

The brute-force approach is straightforward: iterate over all pairs of indices (i, j) and swap whenever |nums[i] - nums[j]| <= limit, repeatedly until no swaps can improve the lexicographic order. While this would eventually produce a correct answer, it is extremely inefficient. The worst-case time complexity would be roughly O(n^2 * n) because each swap operation could involve scanning the entire array repeatedly.

The key insight for an optimal solution is that we can treat indices as nodes in a graph, with an edge between two nodes if |nums[i] - nums[j]| <= limit. Within each connected component of this graph, all elements can be freely swapped among each other. Therefore, the problem reduces to identifying these connected components, sorting the values within each component, and then placing them in the smallest lexicographical order. This can be efficiently achieved using a Union-Find (Disjoint Set Union) data structure.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Swap all valid pairs repeatedly until no improvement; too slow
Optimal O(n log n) O(n) Use Union-Find to group swappable indices, sort within groups, rebuild array

Algorithm Walkthrough

  1. Initialize Union-Find: Create a Union-Find structure with one node for each index in nums. This will track which indices can reach each other through a chain of valid swaps.
  2. Build Connected Components: Iterate through all pairs of adjacent indices (i, i+1) or through all index pairs if needed. If |nums[i] - nums[j]| <= limit, union i and j. This step ensures that all indices that can ultimately swap values belong to the same component.
  3. Group Values by Component: For each index, find its root in the Union-Find. Collect all numbers belonging to the same component into a list.
  4. Sort Each Component: For each component list, sort the values in ascending order. This ensures that when placing numbers back into nums, the smallest numbers go to the smallest indices within the component.
  5. Rebuild the Array: Iterate through nums again. For each index i, find its component, and replace nums[i] with the next smallest value from the sorted component list.

Why it works: The Union-Find guarantees that indices that can reach each other through swaps are grouped together. Sorting each group ensures that the smallest values occupy the smallest indices in the component. Since swaps are allowed arbitrarily within components, this arrangement produces the lexicographically smallest possible array.

Python Solution

from typing import List
from collections import defaultdict
import heapq

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    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):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        else:
            self.parent[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        uf = UnionFind(n)
        
        # Build union-find connections
        for i in range(n):
            for j in range(i+1, n):
                if abs(nums[i] - nums[j]) <= limit:
                    uf.union(i, j)
        
        # Group values by component
        groups = defaultdict(list)
        for i in range(n):
            root = uf.find(i)
            heapq.heappush(groups[root], nums[i])
        
        # Rebuild result array
        result = []
        for i in range(n):
            root = uf.find(i)
            result.append(heapq.heappop(groups[root]))
        
        return result

This implementation creates a Union-Find to track which indices can swap. It then collects numbers by component, sorts them using a min-heap for efficient extraction, and rebuilds the array to ensure lexicographic minimality.

Go Solution

package main

import (
	"container/heap"
)

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}
	return &UnionFind{parent, rank}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
	xRoot, yRoot := uf.Find(x), uf.Find(y)
	if xRoot == yRoot {
		return
	}
	if uf.rank[xRoot] < uf.rank[yRoot] {
		uf.parent[xRoot] = yRoot
	} else {
		uf.parent[yRoot] = xRoot
		if uf.rank[xRoot] == uf.rank[yRoot] {
			uf.rank[xRoot]++
		}
	}
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func lexicographicallySmallestArray(nums []int, limit int) []int {
	n := len(nums)
	uf := NewUnionFind(n)

	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if abs(nums[i]-nums[j]) <= limit {
				uf.Union(i, j)
			}
		}
	}

	groups := make(map[int]*IntHeap)
	for i := 0; i < n; i++ {
		root := uf.Find(i)
		if groups[root] == nil {
			h := &IntHeap{}
			heap.Init(h)
			groups[root] = h
		}
		heap.Push(groups[root], nums[i])
	}

	result := make([]int, n)
	for i := 0; i < n; i++ {
		root := uf.Find(i)
		result[i] = heap.Pop(groups[root]).(int)
	}

	return result
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

The Go implementation mirrors the Python version closely, with explicit heap usage and Go slice handling. Union-Find operations are translated directly, and integer absolute differences are handled with a helper function.

Worked Examples

Example 1: nums = [1,5,3,9,8], limit = 2

  1. Build Union-Find: edges exist between 5-3 and 9-8, creating components [1], [5,3], [9,8].
  2. Group values: {0: [1], 1: [5,3], 3: [9,8]}
  3. Sort groups: {0: [1], 1: [3,5], 3: [8,9]}
  4. Rebuild array: [1,3,5,8,9]

Example 2: nums = [1,7,6,18,2,1], limit = 3

  1. Build components: [0,4,5], [1,2], [3]
  2. Group values: `{0: [1,2,1], 1: [7,6