What is the time complexity of Make Lexicographically Smallest Array by Swapping Elements?

The optimal solution for Make Lexicographically Smallest Array by Swapping Elements runs in O(n log n) time and uses O(n) space. The complexity is dominated by the sorting step, which is O(n log n), while the union-find operations are nearly constant time due to path compression.

What is the brute force solution for Make Lexicographically Smallest Array by Swapping Elements?

The brute force approach for Make Lexicographically Smallest Array by Swapping Elements is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves trying all possible swaps to see if we can create a lexicographically smaller array. This is straightforward but inefficient as it checks every possible pair of indices. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Make Lexicographically Smallest Array by Swapping Elements?

Make Lexicographically Smallest Array by Swapping Elements uses the following concepts: Array, Union-Find, Sorting. The recommended patterns to study are: Union-Find, Sorting, Graph Traversal.

What are the interview tips for Make Lexicographically Smallest Array by Swapping Elements?

Explain your thought process clearly while coding, especially when using data structures like Union-Find. Consider edge cases, such as when no swaps are possible. Practice explaining the time and space complexities of your solution.

What are common mistakes when solving Make Lexicographically Smallest Array by Swapping Elements?

Failing to properly implement the Union-Find structure, leading to incorrect unions. Not considering all pairs for unions, which can lead to missing connections.

#2948

Make Lexicographically Smallest Array by Swapping Elements

Medium

ArrayUnion-FindSortingUnion-FindSortingGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal solution uses a Union-Find (Disjoint Set Union) structure to group elements that can be swapped based on the given limit. This allows us to efficiently find connected components and sort them to achieve the smallest lexicographical order.

⚙️

Algorithm

3 steps

1Step 1: Initialize a Union-Find structure to manage the indices of the array.
2Step 2: For each pair of indices (i, j), if |nums[i] - nums[j]| <= limit, union the two indices.
3Step 3: For each connected component identified by the Union-Find, extract the values, sort them, and then place them back in their respective positions in the original array.

solution.py46 lines

1# Full working Python code
2
3class UnionFind:
4    def __init__(self, size):
5        self.parent = list(range(size))
6        self.rank = [1] * size
7
8    def find(self, x):
9        if self.parent[x] != x:
10            self.parent[x] = self.find(self.parent[x])
11        return self.parent[x]
12
13    def union(self, x, y):
14        rootX = self.find(x)
15        rootY = self.find(y)
16        if rootX != rootY:
17            if self.rank[rootX] > self.rank[rootY]:
18                self.parent[rootY] = rootX
19            elif self.rank[rootX] < self.rank[rootY]:
20                self.parent[rootX] = rootY
21            else:
22                self.parent[rootY] = rootX
23                self.rank[rootX] += 1
24
25
26def make_lexicographically_smallest_array(nums, limit):
27    n = len(nums)
28    uf = UnionFind(n)
29    for i in range(n):
30        for j in range(i + 1, n):
31            if abs(nums[i] - nums[j]) <= limit:
32                uf.union(i, j)
33    components = {}
34    for i in range(n):
35        root = uf.find(i)
36        if root not in components:
37            components[root] = []
38        components[root].append(i)
39    for indices in components.values():
40        values = sorted(nums[i] for i in indices)
41        for index, value in zip(sorted(indices), values):
42            nums[index] = value
43    return nums
44
45# Example usage
46print(make_lexicographically_smallest_array([1, 5, 3, 9, 8], 2))

ℹ

Complexity note: The complexity is dominated by the sorting step, which is O(n log n), while the union-find operations are nearly constant time due to path compression.

1Using Union-Find helps efficiently manage groups of swappable elements.
2Sorting within connected components ensures the smallest lexicographical order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.