2948. Make Lexicographically Smallest Array by Swapping Elements

Problem Description

You are given an array of positive integers nums and a positive integer limit. The array is 0-indexed, which means the elements are referred to by their indices (position) starting from 0. The goal is to perform a series of operations that would lead to the lexicographically smallest array possible.

For each operation, you can choose any pair of indices i and j, and swap the elements at these indices (nums[i] and nums[j]) if the absolute difference between the two elements (|nums[i] - nums[j]|) is less than or equal to the limit. You can perform this operation multiple times.

Your task is to figure out the resulting array that is the lexicographically smallest that can be obtained through these operations. An array is lexicographically smaller than another if at the first differing element, the array has the smaller element.

It is like comparing strings; for example, "abc" is lexicographically smaller than "acd" because they differ at the second character and 'b' comes before 'c'.

Intuition

To solve this problem, we need to find a way to organize the initial array into its lexicographically smallest form given the constraint on the swapping operation.

The intuition behind the solution comes from realizing that within a certain limit, elements of the array can form groups wherein within each group, all the elements can be interchanged.

The main idea is to first sort the array keeping track of the original indices. This sorted pair (arr) consists of tuples, each containing a value from nums and its original index. Sorting this way gives us a picture of how the elements would look in the lexicographically smallest form.

Next, we want to look for blocks or segments in the sorted arr for which all elements in each segment are within the allowed limit for swapping. This means we need to identify contiguous pieces within arr such that every adjacent pair of values is within the limit. Start at the first element and iterate through arr until you come across a pair of elements that violates the limit condition.

Once such a segment is identified, we sort the indices of the elements within that segment. This step assures us that we're placing the smallest available elements into the earliest possible positions in the ans array.

We then fill in the ans array using this sorted indices and the values from the segment that conforms to the limit. After processing a segment, we skip to the next segment and continue the same process until we cover all the elements.

This logic guarantees that within each sortable segment, we arrange the numbers to make the sequence as small as possible, leading to the overall lexicographically smallest array.

Learn more about Union Find and Sorting patterns.

Solution Approach

The solution involves sorting and grouping the original array elements according to the specified limit.

Initially, we create a new array arr that stores tuples, with each tuple composed of a value from nums and its original index. This array arr is then sorted based on the values.

Algorithm steps:

1. Initialize variable n to hold the length of nums.
2. Create arr as a sorted array with elements paired with their original indices.
3. Create an empty array ans to store the final lexicographically smallest array.
4. Set up a loop to traverse through the elements of arr, using variable i as the iterator.
5. Inside the loop, initiate a nested loop (using j) to find the contiguous segment where the adjacent value difference is within the limit.
6. Once the segment is identified, extract the original indices of these elements and sort them. This sorting is based on the original indices of the segment to maintain a lexicographically correct order.
7. Map the values from arr segment to ans using the sorted indices.
8. Continue processing until all elements in nums are considered.

Data structures used include:

• A tuple array to hold the value-index pairs.
• A list to hold the answer, as it enables us to place values at specific indices.

By following this approach, the algorithm ensures we accurately group elements that can be swapped and then sort them in such a way that the resulting array is lexicographically smallest.

Here is an outline of the solution code in Python, touching on the algorithmic steps:

1class Solution:
2    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
3        n = len(nums)                        # Step 1
4        arr = sorted(zip(nums, range(n)))    # Step 2
5        ans = [0] * n                        # Step 3
6        i = 0                                # Step 4
7        while i < n:
8            j = i + 1                        # Step 5
9            while j < n and arr[j][0] - arr[j - 1][0] <= limit:
10                j += 1
11            # Step 6: Get sorted indices for the current segment
12            idx = sorted(k for _, k in arr[i:j])   
13            # Step 7: Mapping values from arr to ans
14            for k, (x, _) in zip(idx, arr[i:j]):  
15                ans[k] = x
16            i = j                            # Step 8
17        return ans   # Return the final lexicographically smallest array

Example Walkthrough

Let's say we have an array nums = [4, 2, 3, 1, 5] and a limit of 1. The task is to find the lexicographically smallest array possible by swapping elements with an absolute difference less than or equal to the limit.

Following the solution approach:

1. We first sort the array with indices: [(1, 3), (2, 1), (3, 2), (4, 0), (5, 4)]
2. Initialize the ans array to hold the final result: ans = [0, 0, 0, 0, 0]

Now we start the algorithm:

• At i = 0, we have the tuple (1, 3). Starting a nested loop with j = i + 1 looking at the tuple (2, 1), we see the difference is within the limit since 2 - 1 <= 1. Thus, we continue to include the element.

• Continuing the inner loop until j = n or we find a pair where the difference is greater than the limit. In this example, since limit is 1, all adjacent elements from i = 0 to j = n satisfy the condition. Hence, j = 5 and the end of the array is reached.

• Next, we obtain and sort the indices from the identified segment: [3, 1, 2, 0, 4].

• We then use the sorted indices to map the sorted values to our answer array ans:

  • ans[3] = 1
  • ans[1] = 2
  • ans[2] = 3
  • ans[0] = 4
  • ans[4] = 5

The process proceeds until the end of the array elements have been considered. In this example, all elements belonged to a single segment since all their differences were within the limit.

The ans array now contains the lexicographically smallest array possible through the given operations: [4, 2, 3, 1, 5] rearranged to [1, 2, 3, 4, 5].

Thus, given the limit, the smallest lexicographical array we can get by swapping elements under the given rules is [1, 2, 3, 4, 5], which is now sorted in ascending order.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed in the following steps:

1. Sorting of the array arr: Sorting n elements has a complexity of O(n log n).
2. The while loop through each element (worst case): Has a linear scan which in the worst-case scenario could touch all elements, making it O(n).
3. Within the while loop, the j index can potentially iterate over all remaining elements, but each element is visited only once due to the external i = j jump. Hence, the inner while loop contributes O(n).
4. Sorting the indices idx for each subarray: This is the tricky part as it depends on the range j - i. However, since every index is considered exactly once due to step 3, we can say that in aggregate it will result in a complexity proportional to O(n log n) over the course of the entire algorithm (considering all chunks).

The combined time complexity, considering the dominant factors and how they run in sequence or are nested, is O(n log n) since sorting dominates the linear passes.

Space Complexity

The space complexity is easier to determine:

1. The arr array to hold sorted values: Requires O(n) space.
2. ans array of size n: Requires O(n) space.
3. Temporary list idx in the worst case might hold n elements: Also contributes O(n).

The combined space complexity, considering additional space used aside from the input, is O(n). There is no space usage that is exponentiated or multiplied by another n, so the space usage grows linearly with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.