Make Lexicographically Smallest Array by Swapping Elements

Medium

Atlassian

0 views

Topics:

ArraysGreedy Algorithms

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.

An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.

Example 1:

Input: nums = [1,5,3,9,8], limit = 2
Output: [1,3,5,8,9]
Explanation: 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]
Explanation: 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]
Explanation: [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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= limit <= 10⁹

Make Lexicographically Smallest Array by Swapping Elements

Medium

Atlassian

0 views

Topics:

ArraysGreedy Algorithms

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.

An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.

Example 1:

Input: nums = [1,5,3,9,8], limit = 2
Output: [1,3,5,8,9]
Explanation: 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]
Explanation: 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]
Explanation: [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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= limit <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array? What is the range of values for the elements within the array?
Are there any restrictions on which elements can be swapped? Is there a separate array or data structure that specifies allowable swap pairs, or is any pair of elements swappable?
If the input array is already lexicographically the smallest possible, should I return the original array, or is there a specific error or success indicator I should return?
What data type are the elements in the array? Are floating point numbers allowed, or are they strictly integers?
Can the input array contain duplicate values, and if so, how should they be handled when trying to minimize the array lexicographically?

Brute Force Solution

Approach

The basic idea is to try every single possible combination of swaps to see which arrangement gives us the smallest possible result when comparing the array as a whole. We're exploring all options, like trying every possible key on a keychain to see which one opens a lock.

Here's how the algorithm would work step-by-step:

Start with the original arrangement of the numbers.
Consider swapping the first number with every other number in the array, one at a time, creating a new arrangement each time.
For each of those new arrangements, consider all possible swaps you can make in that arrangement, again creating new arrangements.
Continue doing this, making swaps on swaps on swaps, exploring all possible sequences of swaps.
After each swap, or after a sequence of swaps, compare the current arrangement to the best arrangement you've seen so far. The "best" arrangement is the one that comes first alphabetically, just like in a dictionary.
If the current arrangement is better (smaller), remember it as the new best arrangement.
After trying every possible combination of swaps, the arrangement you've remembered as the best is the answer.

Code Implementation

def make_lexicographically_smallest_array_brute_force(original_array):
    best_array_so_far = original_array[:] # Start with a copy of the original

    def find_smallest_arrangement(current_array):
        nonlocal best_array_so_far
        is_smaller = current_array < best_array_so_far

        # Update the best array if the current array is smaller lexicographically
        if is_smaller:

            best_array_so_far = current_array[:]

        for first_index in range(len(current_array)): 
            for second_index in range(first_index + 1, len(current_array)):

                # Create a new array by swapping elements at two indices
                new_array = current_array[:]
                new_array[first_index], new_array[second_index] = new_array[second_index], new_array[first_index]

                # Recursively explore all possible arrangements after the swap
                find_smallest_arrangement(new_array)

    find_smallest_arrangement(original_array[:])

    # After trying all possible swaps, return the lexicographically smallest array
    return best_array_so_far

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n!) – The algorithm attempts all possible swaps to find the lexicographically smallest array. In the worst case, it explores all permutations of the array. Generating all possible permutations of an array of size n takes O(n!) time. This is because there are n! possible arrangements of the elements, and the algorithm, in principle, checks them all.

Space Complexity

O(N!) – The plain English explanation suggests exploring all possible arrangements of the array through swaps, which implies generating permutations. Storing all these permutations requires significant space. In the worst-case scenario, where N is the size of the input array, there are N! (N factorial) possible permutations. The algorithm keeps track of the 'best arrangement so far', and in the process of exploring all possible combinations of swaps, it implicitly maintains or generates many other arrangements. Therefore the space needed to store or represent these intermediate and final arrangements grows factorially with the input size, leading to O(N!) auxiliary space.

Optimal Solution

Approach

The goal is to rearrange the initial order of numbers to obtain the smallest arrangement possible, but only by swapping numbers according to specified rules. We find connected groups of numbers that can be freely reordered, and within each group, sort the numbers from smallest to largest.

Here's how the algorithm would work step-by-step:

Identify all the groups of positions where numbers can be swapped around.
For each group, collect all the numbers located at those positions.
Sort those collected numbers in ascending order from smallest to largest.
Place the sorted numbers back into their original positions within the group, ensuring the smallest number goes to the earliest position and so on.
By doing this for every group, we ensure that each group's numbers are arranged in the smallest possible order, ultimately resulting in the lexicographically smallest total arrangement.

Code Implementation

def make_lexicographically_smallest_array(initial_array, can_swap):
    array_length = len(initial_array)
    visited = [False] * array_length
    
    def depth_first_search(index, current_group_indices):
        visited[index] = True
        current_group_indices.append(index)
        for neighbor_index in range(array_length):
            if can_swap[index][neighbor_index] and not visited[neighbor_index]:
                depth_first_search(neighbor_index, current_group_indices)

    for index in range(array_length):
        if not visited[index]:
            # Find all indices that can be swapped within this connected component.
            current_group_indices = []
            depth_first_search(index, current_group_indices)
            
            # Collect the values at these indices.
            group_values = [initial_array[i] for i in current_group_indices]
            
            # Sort the values to achieve lexicographical order.
            group_values.sort()
            
            current_group_indices.sort()
            # Place the sorted values back into the array.
            for i, index_value in enumerate(current_group_indices):
                initial_array[index_value] = group_values[i]
    
    return initial_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm involves identifying connected groups of swappable positions, which can be done using techniques like Depth First Search (DFS) or Disjoint Set Union (DSU). Assuming we use either of those techniques, the complexity for finding the connected groups is near linear, or O(n*alpha(n)) which approximates to O(n) where n is the number of elements in the array. Then, for each connected group, we collect the elements, sort them (using an efficient sorting algorithm like merge sort or quicksort with average case complexity O(k log k) where k is the size of the group), and place them back. Since in the worst case, a single group could contain all n elements, the overall complexity is dominated by the sorting step. Therefore, the overall time complexity becomes O(n log n) in the worst case.

Space Complexity

O(N) – The algorithm identifies groups of swappable positions, collects numbers from those positions, and sorts them. In the worst case, all positions might be part of a single group, requiring an auxiliary list to store all N numbers. Similarly, the positions themselves might be stored in a list of size N. Thus, the dominant space usage is proportional to the input size N.

Edge Cases

Case	How to Handle
Null or empty input array	Return the input array directly as there's nothing to process, or throw an IllegalArgumentException if modification is not permitted on null/empty arrays.
Array with only one element	Return the array as is, since no swaps are possible to make it lexicographically smaller.
Array already sorted in ascending order	Return the array unchanged as it is already the lexicographically smallest.
Large input array size causing potential memory issues (e.g., exceeding memory limits)	Evaluate the space complexity of the union-find data structure or alternative approaches and ensure sufficient memory allocation, potentially employing techniques like path compression and union by rank in union-find to reduce memory usage.
Values in 'allowedSwaps' contain out-of-bounds indices (indices outside of the input array length)	Validate each index in 'allowedSwaps' to ensure it's within the valid range [0, array.length - 1] before processing it, potentially skipping or throwing an exception if it's out of bounds.
Cycles in 'allowedSwaps' where indices form a closed loop of allowed swaps	Union-find correctly handles cycles by merging all connected components into a single set, ensuring all elements within the cycle can be reordered.
Extreme value ranges of numbers in the array (very large positive or negative numbers)	Consider potential integer overflow issues during comparisons or calculations, and use appropriate data types (e.g., long) or modular arithmetic if necessary.
A subset of the array elements cannot be swapped with other elements, resulting in multiple independent swap groups	Union-find correctly identifies and manages independent swap groups, ensuring only elements within each group are reordered locally to achieve lexicographical minimization.