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
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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

1from typing import List
2
3class Solution:
4    def lexicographically_smallest_array(self, nums: List[int], limit: int) -> List[int]:
5        # This is the length of the input list
6        length = len(nums)
7      
8        # Create a sorted list of tuples where each tuple contains
9        # an element from the input list and its corresponding index
10        num_with_index = sorted(zip(nums, range(length)))
11      
12        # Initialize an output list with the same size as the input list
13        result = [0] * length
14      
15        i = 0
16        # Iterate through the sorted numbers along with their indices
17        while i < length:
18            j = i + 1
19            # Seek for a subsequence where the difference between any
20            # two consecutive elements does not exceed the limit
21            while j < length and num_with_index[j][0] - num_with_index[j - 1][0] <= limit:
22                j += 1
23          
24            # Extract the indices for the subsequence found above
25            indices = sorted(index for _, index in num_with_index[i:j])
26          
27            # Assign the sorted elements to their original positions
28            # in the output list based on the subsequence indices
29            for k, (num, _) in zip(indices, num_with_index[i:j]):
30                result[k] = num
31          
32            # Move to the next subsequence
33            i = j
34      
35        return result
36
37# The code can be used as follows:
38# solution_instance = Solution()
39# result = solution_instance.lexicographically_smallest_array([some list], limit)
40# where [some list] is a list of integers and limit is the maximum allowed difference
41
1import java.util.Arrays;
2import java.util.Comparator;
3
4class Solution {
5    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
6        // Get the length of the original array.
7        int n = nums.length;
8      
9        // Create an array of indices of the given array.
10        Integer[] indices = new Integer[n];
11        for (int i = 0; i < n; ++i) {
12            indices[i] = i;
13        }
14      
15        // Sort the indices based on the values in 'nums' they point to.
16        Arrays.sort(indices, Comparator.comparingInt(i -> nums[i]));
17      
18        // Prepare an array to store the answer.
19        int[] answer = new int[n];
20      
21        // Loop over the indices array.
22        for (int i = 0; i < n;) {
23            // Find a contiguous subsequence of indices where each pair of consecutive
24            // numbers has a difference less than or equal to 'limit'.
25            int j = i + 1;
26            while (j < n && nums[indices[j]] - nums[indices[j - 1]] <= limit) {
27                ++j;
28            }
29          
30            // Copy the subrange of indices [i, j) to a temporary array 'tempIndices'.
31            Integer[] tempIndices = Arrays.copyOfRange(indices, i, j);
32          
33            // Sort the temporary indices array in natural order, effectively sorting by
34            // their original positions in 'nums'.
35            Arrays.sort(tempIndices, Comparator.naturalOrder());
36          
37            // Populate the 'answer' array with values from 'nums' using the sorted
38            // temporary indices.
39            for (int k = i; k < j; ++k) {
40                answer[tempIndices[k - i]] = nums[indices[k]];
41            }
42          
43            // Move to the next subsequence.
44            i = j;
45        }
46      
47        return answer;
48    }
49}
50
1#include <vector>
2#include <numeric>
3#include <algorithm>
4
5class Solution {
6public:
7    // Method to find lexicographically smallest array based on the given rules.
8    std::vector<int> lexicographicallySmallestArray(std::vector<int>& nums, int limit) {
9        int n = nums.size(); // Size of the input array
10        std::vector<int> indices(n); // Array to hold indices 0 .. n-1
11        std::iota(indices.begin(), indices.end(), 0); // Fill indices array with 0 .. n-1
12
13        // Sort the indices based on the value at the index in non-decreasing order
14        std::sort(indices.begin(), indices.end(), [&](int i, int j) {
15            return nums[i] < nums[j];
16        });
17
18        std::vector<int> ans(n); // To store the final answer
19
20        // Process each group of indices
21        for (int i = 0; i < n;) {
22            int j = i + 1;
23            // Find the range of indices where the difference of values
24            // is within the given 'limit'
25            while (j < n && nums[indices[j]] - nums[indices[j - 1]] <= limit) {
26                ++j;
27            }
28
29            // Extract the subarray of indices for current group
30            std::vector<int> temp(indices.begin() + i, indices.begin() + j);
31            // Sort the subarray of indices to rearrange in lexicographically
32            // smallest order according to the problem statement
33            std::sort(temp.begin(), temp.end());
34
35            // Assign sorted values to the ans array based on the sorted indices
36            for (int k = i; k < j; ++k) {
37                ans[temp[k - i]] = nums[indices[k]];
38            }
39            // Move to the next group
40            i = j;
41        }
42        return ans; // Return the resulting lexicographically smallest array
43    }
44};
45
1function lexicographicallySmallestArray(nums: number[], limit: number): number[] {
2    // Get the length of the `nums` array
3    const length: number = nums.length;
4    // Create an array of indices for the `nums` array
5    const indices: number[] = nums.map((_, index) => index);
6    // Sort the indices by comparing the values in `nums` they refer to
7    indices.sort((i, j) => nums[i] - nums[j]);
8    // Initialize the answer array with zeros
9    const answer: number[] = new Array(length).fill(0);
10
11    // Iterate over the sorted indices
12    for (let i = 0; i < length; ) {
13        // Find a contiguous group of indices within the `limit`
14        let j = i + 1;
15        while (j < length && nums[indices[j]] - nums[indices[j - 1]] <= limit) {
16            j++;
17        }
18        // Sort the slice of `indices` by their values (not by the values they refer to in `nums`)
19        const sortedIndicesSlice: number[] = indices.slice(i, j).sort((a, b) => a - b);
20        // Assign the values from `nums` to the `answer` array based on the sorted slice of indices
21        for (let k = i; k < j; k++) {
22            answer[sortedIndicesSlice[k - i]] = nums[indices[k]];
23        }
24        // Move to the next group of indices
25        i = j;
26    }
27    // Return the lexicographically smallest array
28    return answer;
29}
30

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.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄