1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
Problem Description
The goal is to calculate the minimum number of adjacent digit swaps needed to transform a given string num
, which represents a large integer, into its k-th smallest wonderful integer. A wonderful integer is a permutation of the digits in num
that is greater than num
. In essence, we want to find the k-th permutation of num
that is greater than num
itself, and then determine how many swaps of adjacent digits are needed to achieve that specific permutation starting from num
.
For example, if num
is "1234" and k is 1, the next wonderful integer is "1243", and at least one swap (swapping '3' and '4') is necessary to reach it from "1234".
The problem statement also implies that there is a guaranteed k-th smallest wonderful integer for the given num
and k
.
Intuition
To solve this problem, we employ two key steps:
- Generate the k-th smallest wonderful integer by finding k successive next permutations of the original number.
- Count the minimum swaps needed to convert the original number to this k-th permutation.
To achieve the first step, we use the concept of next permutation which follows this algorithm:
- Traverse the digits from right to left until you find a digit (let's call it the pivot) that is smaller than its immediate right neighbor. This is because for any arrangement to be the next permutation, there has to be an increase in the magnitude and this can only happen if we find such a pivot.
- Find the smallest digit on the right side of the pivot that is greater than the pivot.
- Swap this smallest digit with the pivot.
- Reverse the digits to the right of the pivot to get the next immediate permutation.
This algorithm ensures that we get the next greater permutation with the minimal increase in value. We repeat this process k times to get the k-th smallest wonderful integer.
The second step is essentially about counting the number of inversion pairs which essentially means counting how many indices must be swapped to sort an array. An inversion pair is a pair of indices (i, j)
such that i < j
and arr[i] > arr[j]
. In our case, arr
represents the indices of the digits in the k-th permutation when mapped back to the indices of the original number. For a given digit in the k-th permutation, we find the earliest occurrence of that digit in the original number that has not been used yet. The process counts how many greater digits have been "bypassed" and thus need to be swapped to move the digit to its required position in the k-th permutation.
If num
contains repeated digits, we use auxiliary arrays to keep track of the occurrences of each digit, since simply mapping digits to indices won't be enough due to repetitions. We need to carefully select the appropriate digit occurrences to minimize the total swap count, which leads to selecting the earliest unused occurrence of each digit.
The overall intuition involves a clever use of the next permutation algorithm to find the target number, followed by a detailed but straightforward swap count using the concept of inversion pairs.
Learn more about Greedy and Two Pointers patterns.
Solution Approach
The solution approach encompasses two major algorithms: generating the next permutation and counting inversion pairs.
Generating the Next Permutation
The function next_permutation
operates on a list of characters representing digits of the number. The algorithm to produce the next greater permutation is as follows:
- Start by finding the rightmost digit (
i
) that is less than the digit immediately to its right. This step identifies the pivot for swapping. - Next, locate the rightmost digit (
j
) that is greater than the pivot (i
) found in the previous step. This is the smallest digit that can be swapped with the pivot to create a larger number. - Swap the pivot (
i
) with the digit (j
) located in the second step. - Finally, reverse the sequence of digits to the right of the original pivot's position to get them in the lowest possible order.
This function is called k
times iteratively to land upon the k-th smallest wonderful integer s
.
Counting Inversion Pairs
Once we have the k-th permutation s
, we need to calculate the swaps needed to get num
to s
. We use an array arr
to keep track of where each digit from s
should come from in num
. The mapping of digits to indices accounts for the possibility of duplicate digits.
- Maintain a 2D list
d
, whered[j]
holds the list of indices where the digitj
appears in the original numbernum
. - Also, keep an index array
idx
of size 10 (since there are 10 possible digits) that helps select the next available occurrence of each digit. - For each digit
c
ins
, find its index innum
usingd[j][idx[j]]
and incrementidx[j]
. This arrayarr
now represents a sequence of indices fromnum
constituting the permutations
. - To get the number of swaps, we find the number of inversion pairs in the array
arr
. An inversion pair between indicesi
andj
occurs ifi < j
andarr[i] > arr[j]
. The sum of these pairs indicates the total number of swaps needed.
1class Solution:
2 def getMinSwaps(self, num: str, k: int) -> int:
3 # Function to generate the next permutation
4 def next_permutation(nums: List[str]) -> bool:
5 n = len(nums)
6 i = n - 2
7
8 # Locate the pivot
9 while i >= 0 and nums[i] >= nums[i + 1]:
10 i -= 1
11 if i < 0:
12 return False
13 j = n - 1
14
15 # Locate the rightmost successor
16 while j >= 0 and nums[j] <= nums[i]:
17 j -= 1
18 nums[i], nums[j] = nums[j], nums[i]
19
20 # Reverse the suffix
21 nums[i + 1 : n] = nums[i + 1 : n][::-1]
22 return True
23
24 # Convert the original number to a list for easier manipulation
25 s = list(num)
26 # Apply the next permutation k times
27 for _ in range(k):
28 next_permutation(s)
29
30 # Initialize structures to keep track of digit occurrences
31 d = [[] for _ in range(10)]
32 idx = [0] * 10
33 n = len(s)
34 for i, c in enumerate(num):
35 j = ord(c) - ord("0")
36 d[j].append(i)
37
38 arr = [0] * n
39 for i, c in enumerate(s):
40 j = ord(c) - ord("0")
41 arr[i] = d[j][idx[j]]
42 idx[j] += 1
43
44 # Count inversion pairs
45 return sum(arr[j] > arr[i] for i in range(n) for j in range(i))
This two-phase algorithm efficiently gets to the solution by producing the required permutation and then evaluating the movement from the original to the target permutation.
Optimizations
While the current solution is straightforward, optimizations can be made to the inversion pair counting phase to gain performance. One technique is to use a Binary Indexed Tree (BIT) or a Fenwick tree to count inversions, which can reduce the time complexity of finding inversion pairs from O(n^2)
to O(n log n)
.
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 walk through this solution approach with a small example. Suppose our starting string num
is "132" and we are tasked with finding the 1st smallest wonderful integer and the minimum amount of swaps to achieve it.
Generating the Next Permutation
We begin by following the algorithm's steps to find the next permutation, which we will do one time because k=1
.
- Starting from the rightmost digit, we look for the first digit that is smaller than the one immediately after it. Here it's '1' (since '3' is larger than '1' and '2' is not larger than '3').
- Now, we look for the smallest digit to the right of '1' that's larger than '1'; this is '2'.
- We swap '1' and '2', making our number "231".
- Finally, we reverse any digits right of the original pivot, but since '2' and '3' are the only digits to the right and we just swapped them, the step is not needed.
Our next permutation is "231". Since we only need to find the 1st smallest wonderful integer, we are done with this phase.
Counting Inversion Pairs
Now we must determine how many swaps it will take to turn "132" into "231".
- We track where each digit from "231" should come from in "132". In "132", the '2' is in position 2, '3' is in position 1, and '1' is in position 0.
- So we have an array
arr
representing the sequence of indices: [2, 1, 0]. - Now, we count the inversion pairs. An inversion pair is a pair
(i, j)
wherei < j
andarr[i] > arr[j]
. We have two inversion pairs here: (2, 1) and (2, 0) becausearr[2]
is greater thanarr[1]
andarr[0]
.
The number of inversion pairs tells us that at least two swaps are needed to arrange "132" into "231". The swaps are:
- Swap '1' and '3' to get "312".
- Swap '1' and '2' to get "231".
Thus, the minimum number of swaps required is 2.
Solution Implementation
1from typing import List
2
3class Solution:
4 def getMinSwaps(self, num: str, k: int) -> int:
5 # Helper function to generate the next lexicographically greater permutation
6 def next_permutation(nums: List[str]) -> bool:
7 n = len(nums)
8 i = n - 2
9
10 # Find the first element, nums[i], which is smaller than the element to its right
11 while i >= 0 and nums[i] >= nums[i + 1]:
12 i -= 1
13
14 # If there is no such element, all permutations have been generated
15 if i < 0:
16 return False
17
18 # Find the first element to the right, nums[j], which is greater than nums[i]
19 j = n - 1
20 while nums[j] <= nums[i]:
21 j -= 1
22
23 # Swap nums[i] and nums[j]
24 nums[i], nums[j] = nums[j], nums[i]
25
26 # Reverse the sequence from nums[i+1] up to the last element
27 nums[i + 1:] = reversed(nums[i + 1:])
28
29 return True
30
31 # Convert the string number to a list of characters
32 s = list(num)
33
34 # Generate the k-th permutation
35 for _ in range(k):
36 next_permutation(s)
37
38 # Create a list of lists to hold indices for each digit
39 digit_indices = [[] for _ in range(10)]
40 current_indices = [0] * 10
41 n = len(s)
42
43 # Populate digit_indices with the original indices of each digit in 'num'
44 for i, char in enumerate(num):
45 digit = int(char)
46 digit_indices[digit].append(i)
47
48 # Array to store the original indices of each digit in the k-th permutation
49 original_indices = [0] * n
50 for i, char in enumerate(s):
51 digit = int(char)
52 original_indices[i] = digit_indices[digit][current_indices[digit]]
53 current_indices[digit] += 1
54
55 # Count the minimum number of swaps to transform the original number to
56 # the k-th permutation by comparing the original indices in the k-th permutation
57 return sum(original_indices[j] > original_indices[i] for i in range(n) for j in range(i))
58
1class Solution {
2
3 // Main function to find the minimum number of swaps to reach the k-th permutation
4 public int getMinSwaps(String num, int k) {
5 char[] chars = num.toCharArray(); // Convert string to character array for manipulation
6
7 // Advance to the k-th next permutation of the string
8 for (int i = 0; i < k; ++i) {
9 getNextPermutation(chars);
10 }
11
12 // Create a list to store indices for each digit
13 List<Integer>[] digitIndices = new List[10];
14 Arrays.setAll(digitIndices, i -> new ArrayList<>());
15 int n = chars.length;
16
17 // Fill each list with indices where the digit appears in the original string
18 for (int i = 0; i < n; ++i) {
19 digitIndices[num.charAt(i) - '0'].add(i);
20 }
21
22 int[] indexCounter = new int[10]; // Index counter for each digit
23 int[] mappedIndices = new int[n]; // To store the index mapping of the k-th permutation
24
25 // Map characters in k-th permutation to their original indices
26 for (int i = 0; i < n; ++i) {
27 int digit = chars[i] - '0';
28 mappedIndices[i] = digitIndices[digit].get(indexCounter[digit]++);
29 }
30
31 // Count the number of swaps needed to transform original string to k-th permutation
32 int swapCount = 0;
33 for (int i = 0; i < n; ++i) {
34 for (int j = 0; j < i; ++j) {
35 if (mappedIndices[j] > mappedIndices[i]) {
36 swapCount++;
37 }
38 }
39 }
40
41 return swapCount;
42 }
43
44 // Helper function to generate the next lexicographical permutation
45 private boolean getNextPermutation(char[] nums) {
46 int n = nums.length;
47 int i = n - 2;
48
49 // Find the first character which is smaller than its next one
50 while (i >= 0 && nums[i] >= nums[i + 1]) {
51 --i;
52 }
53
54 // If no such character is found, there's no next permutation
55 if (i < 0) {
56 return false;
57 }
58
59 // Find a character which is larger than nums[i] to swap with
60 int j = n - 1;
61 while (j >= 0 && nums[i] >= nums[j]) {
62 --j;
63 }
64
65 // Swap the found characters
66 swapElements(nums, i++, j);
67
68 // Reverse the sequence after the initially found position i
69 for (j = n - 1; i < j; ++i, --j) {
70 swapElements(nums, i, j);
71 }
72
73 return true;
74 }
75
76 // Helper function to swap characters at index i and j in the array
77 private void swapElements(char[] nums, int i, int j) {
78 char temp = nums[i];
79 nums[i] = nums[j];
80 nums[j] = temp;
81 }
82}
83
1class Solution {
2public:
3 // Method to calculate the minimum number of swaps needed to
4 // transform the original string 'num' into its k-th permutation.
5 int getMinSwaps(string num, int k) {
6 string permutation = num;
7
8 // Generate the k-th permutation of the input string
9 for (int i = 0; i < k; ++i) {
10 next_permutation(permutation.begin(), permutation.end());
11 }
12
13 // Create an array of vectors to keep track of the indices of each digit in the original num string.
14 // Each index represents a digit from 0 to 9, and we store all the indices of these digits from 'num'.
15 vector<int> digitIndices[10]; // Assuming 'num' consists of only digits 0-9
16 int n = num.size(); // Length of the input string
17 for (int i = 0; i < n; ++i) {
18 digitIndices[num[i] - '0'].push_back(i);
19 }
20
21 // Array to keep next available index for each digit.
22 int nextIndex[10] = {0};
23
24 // Array to store the desired positions for each digit to form the k-th permutation.
25 vector<int> desiredPositions(n);
26 for (int i = 0; i < n; ++i) {
27 int digit = permutation[i] - '0';
28 desiredPositions[i] = digitIndices[digit][nextIndex[digit]++];
29 }
30
31 // Calculate the minimum number of swaps by determining the number of inversions.
32 int minSwaps = 0;
33 for (int i = 0; i < n; ++i) {
34 for (int j = 0; j < i; ++j) {
35 // If any number at index j should come after number at index i in the k-th permutation,
36 // it is an inversion and needs a swap.
37 if (desiredPositions[j] > desiredPositions[i]) {
38 minSwaps++;
39 }
40 }
41 }
42
43 return minSwaps; // Return the minimum number of swaps needed
44 }
45};
46
1function getMinSwaps(num: string, k: number): number {
2 // Length of the number string
3 const numLength = num.length;
4 // Convert the original number string into an array of characters
5 const numArray = num.split('');
6
7 // Generate the k-th permutation
8 for (let i = 0; i < k; ++i) {
9 nextPermutation(numArray);
10 }
11
12 // Create an array to store indices for each digit
13 const digitIndices: number[][] = Array.from({ length: 10 }, () => []);
14
15 // Fill the array with the indices of each digit in the original number
16 for (let i = 0; i < numLength; ++i) {
17 digitIndices[+num[i]].push(i);
18 }
19
20 // Array to keep track of the next index for each digit
21 const nextIndex: number[] = Array(10).fill(0);
22
23 // Array to hold the indices of the k-th permutation in the original number's order
24 const permutedIndices: number[] = [];
25
26 // Fill in the permutedIndices using the digitIndices and nextIndex to track
27 for (let i = 0; i < numLength; ++i) {
28 permutedIndices.push(digitIndices[+numArray[i]][nextIndex[+numArray[i]]++]);
29 }
30
31 // Counter for the minimum number of swaps
32 let minSwaps = 0;
33
34 // Calculate the number of swaps required
35 for (let i = 0; i < numLength; ++i) {
36 for (let j = 0; j < i; ++j) {
37 // If the index of the current digit is less than that of the previous digit, a swap would be required
38 if (permutedIndices[j] > permutedIndices[i]) {
39 minSwaps++;
40 }
41 }
42 }
43
44 // Return the calculated minimum number of swaps
45 return minSwaps;
46}
47
48function nextPermutation(nums: string[]): boolean {
49 // Get the length of the array
50 const n = nums.length;
51 // Find the first index from the end where the previous element is smaller than the current element
52 let i = n - 2;
53 while (i >= 0 && nums[i] >= nums[i + 1]) {
54 i--;
55 }
56 // If no such index exists, the permutation is the last one in order
57 if (i < 0) {
58 return false;
59 }
60 // Find the first element from the end that is greater than the element at index 'i'
61 let j = n - 1;
62 while (j >= 0 && nums[i] >= nums[j]) {
63 j--;
64 }
65 // Swap the elements at indices 'i' and 'j'
66 [nums[i], nums[j]] = [nums[j], nums[i]];
67 // Reverse the sub-array from index 'i+1' to the end
68 for (i = i + 1, j = n - 1; i < j; ++i, --j) {
69 [nums[i], nums[j]] = [nums[j], nums[i]];
70 }
71 // Return true as the next permutation has been formed
72 return true;
73}
74
Time and Space Complexity
Time Complexity
The time complexity of the function getMinSwaps
can be analyzed as follows:
- The
next_permutation
function has a time complexity ofO(n)
since it involves a reversed single pass through the listnums
to find the pivot (i
) and the swap position (j
), followed by a reverse of a subarray which all together take linear time. - This
next_permutation
function is called exactlyk
times in a loop. Each call operates on the lists
which represents the number permutation, making the complexityO(k*n)
. - After obtaining the
k-th
permutation, the function performs some setup for an arrayd
and an arrayidx
, where each is indexed by digits 0-9. This takesO(1)
since the number of digits is constant. - The list
arr
is populated within a loop overs
, takingO(n)
time. - Finally, there is a nested loop structure that counts the number of swaps, which has a quadratic time complexity
O(n^2)
within the outern
loop.
Matching this against the provided reference answer, we see that the total time complexity has two main contributions: O(k*n)
for the repeated next-permutation generation and O(n^2)
for the swaps counting. Therefore, the overall time complexity is O(n * (k + n))
.
Space Complexity
The space complexity is as follows:
- Space is used for the list
s
which is a conversion of the input number to a list of single digits, takingO(n)
space. - The
arr
array also usesO(n)
space. - The
d
list of lists, although indexed by the number of potential digits (0-9), uses a total ofO(n)
space since it stores positions of each digit in the input number. - The
idx
array is a fixed size of 10, thusO(1)
.
Since O(n)
is the dominating factor, the overall space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
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