#2948

Medium

LeetCode Problem Workspace

Make Lexicographically Smallest Array by Swapping Elements

Solve the problem of making an array lexicographically smallest through element swaps under a limit constraint.

Problem Statement

You are given a 0-indexed array of positive integers nums and a positive integer limit. In one operation, you can swap any two elements nums[i] and nums[j] if the absolute difference between them is less than or equal to limit.

Your task is to return the lexicographically smallest array that can be obtained by performing the operation any number of times. The solution should efficiently group and sort the elements where applicable, ensuring the lexicographical order is minimized.

Examples

Example 1

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

Output: [1,3,5,8,9]

Apply the operation 2 times:

Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8]
Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9] We cannot obtain a lexicographically smaller array by applying any more operations. Note that it may be possible to get the same result by doing different operations.

Example 2

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

Output: [1,6,7,18,1,2]

Apply the operation 3 times:

Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1]
Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1]
Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2] We cannot obtain a lexicographically smaller array by applying any more operations.

Example 3

Input: nums = [1,7,28,19,10], limit = 3

Output: [1,7,28,19,10]

[1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= limit <= 109

Solution Approach

Union Find for Grouping

First, use the Union Find (Disjoint Set Union) data structure to identify which elements can be swapped. Each element is treated as a node, and an edge is formed between nodes if the difference between the corresponding elements is less than or equal to the given limit. By doing this, you create connected components of swappable elements.

Sorting Each Component

After grouping elements using Union Find, sort the elements within each connected component. Sorting ensures that each group of connected elements is ordered lexicographically smallest, which contributes to the overall array's smallest lexicographical arrangement.

Rebuild the Array

Finally, for each group of connected components, place the sorted elements back into their original positions in the array. This way, the final array respects the lexicographical order while satisfying the swap constraint imposed by the limit.

Complexity Analysis

Metric	Value
Time	O(N \cdot \log N)
Space	O(N + S_N) \approx O(N)

The time complexity of the solution is O(N * log N) due to sorting the components. The Union Find operations (path compression and union by rank) run in nearly constant time, leading to an overall complexity of O(N * log N). The space complexity is O(N) to store the Union Find structure and the array of components, plus the sorted data for each component.

What Interviewers Usually Probe

Check if the candidate can correctly implement Union Find and sort the connected components.
Evaluate their understanding of the problem by asking how they'd handle edge cases, such as when no swaps are possible.
Test their ability to explain and optimize the approach in terms of time and space complexity.

Common Pitfalls or Variants

Common pitfalls

Not using Union Find correctly, leading to incorrect grouping of swappable elements.
Failing to sort each group independently after identifying the connected components.
Overcomplicating the solution by trying to perform swaps directly without first sorting the connected components.

Follow-up variants

Change the swap condition to allow only certain elements to be swapped (e.g., based on parity or value range).
Extend the problem to handle arrays with negative numbers or arrays of arbitrary size.
Incorporate a step to track the number of swap operations or enforce a limited number of swaps.

FAQ

How can Union Find help with the 'Make Lexicographically Smallest Array by Swapping Elements' problem?

Union Find helps by efficiently grouping elements that can be swapped based on the difference constraint, allowing you to focus on sorting each connected group of elements.

What is the time complexity of the solution?

The time complexity is O(N * log N) due to sorting the elements within each connected component, where N is the length of the array.

Can the Union Find approach work for any type of array?

Yes, the Union Find approach can be applied to any array as long as the swap condition based on the difference limit holds.

How does sorting each component help in the solution?

Sorting ensures that each connected group of elements is placed in its lexicographically smallest order, contributing to the smallest possible overall array.

What if no swaps are possible in the problem?

If no swaps are possible, the array is already in its lexicographically smallest form, and the solution simply returns the original array.

terminal

Solution

Solution 1: Sorting

According to the problem description, the sorted array $\textit{nums}$ can be partitioned into several subarrays such that the difference between adjacent elements in each subarray does not exceed $\textit{limit}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        arr = sorted(zip(nums, range(n)))
        ans = [0] * n
        i = 0
        while i < n:
            j = i + 1
            while j < n and arr[j][0] - arr[j - 1][0] <= limit:
                j += 1
            idx = sorted(k for _, k in arr[i:j])
            for k, (x, _) in zip(idx, arr[i:j]):
                ans[k] = x
            i = j
        return ans

Continue Practicing

#2503 maximum number of points from grid queries #2421 number of good paths #1998 gcd sort of an array