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:
- Initialize variable
n
to hold the length ofnums
. - Create
arr
as a sorted array with elements paired with their original indices. - Create an empty array
ans
to store the final lexicographically smallest array. - Set up a loop to traverse through the elements of
arr
, using variablei
as the iterator. - Inside the loop, initiate a nested loop (using
j
) to find the contiguous segment where the adjacent value difference is within thelimit
. - 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.
- Map the values from
arr
segment toans
using the sorted indices. - 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:
class Solution:
def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
n = len(nums) # Step 1
arr = sorted(zip(nums, range(n))) # Step 2
ans = [0] * n # Step 3
i = 0 # Step 4
while i < n:
j = i + 1 # Step 5
while j < n and arr[j][0] - arr[j - 1][0] <= limit:
j += 1
# Step 6: Get sorted indices for the current segment
idx = sorted(k for _, k in arr[i:j])
# Step 7: Mapping values from arr to ans
for k, (x, _) in zip(idx, arr[i:j]):
ans[k] = x
i = j # Step 8
return ans # Return the final lexicographically smallest array
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
- We first sort the array with indices:
[(1, 3), (2, 1), (3, 2), (4, 0), (5, 4)]
- 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 withj = i + 1
looking at the tuple(2, 1)
, we see the difference is within the limit since2 - 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, sincelimit
is 1, all adjacent elements fromi = 0
toj = 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:
- Sorting of the array
arr
: Sortingn
elements has a complexity ofO(n log n)
. - 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)
. - Within the while loop, the
j
index can potentially iterate over all remaining elements, but each element is visited only once due to the externali = j
jump. Hence, the inner while loop contributesO(n)
. - Sorting the indices
idx
for each subarray: This is the tricky part as it depends on the rangej - 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 toO(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:
- The
arr
array to hold sorted values: RequiresO(n)
space. ans
array of sizen
: RequiresO(n)
space.- Temporary list
idx
in the worst case might holdn
elements: Also contributesO(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.
How many times is a tree node visited in a depth first search?
Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!