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:

1. Generate the k-th smallest wonderful integer by finding k successive next permutations of the original number.
2. 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, where d[j] holds the list of indices where the digit j appears in the original number num.
• 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 in s, find its index in num using d[j][idx[j]] and increment idx[j]. This array arr now represents a sequence of indices from num constituting the permutation s.
• To get the number of swaps, we find the number of inversion pairs in the array arr. An inversion pair between indices i and j occurs if i < j and arr[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).

Example 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.

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').
2. Now, we look for the smallest digit to the right of '1' that's larger than '1'; this is '2'.
3. We swap '1' and '2', making our number "231".
4. 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".

1. 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.
2. So we have an array arr representing the sequence of indices: [2, 1, 0].
3. Now, we count the inversion pairs. An inversion pair is a pair (i, j) where i < j and arr[i] > arr[j]. We have two inversion pairs here: (2, 1) and (2, 0) because arr[2] is greater than arr[1] and arr[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

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 of O(n) since it involves a reversed single pass through the list nums 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 exactly k times in a loop. Each call operates on the list s which represents the number permutation, making the complexity O(k*n).
• After obtaining the k-th permutation, the function performs some setup for an array d and an array idx, where each is indexed by digits 0-9. This takes O(1) since the number of digits is constant.
• The list arr is populated within a loop over s, taking O(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 outer n 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, taking O(n) space.
• The arr array also uses O(n) space.
• The d list of lists, although indexed by the number of potential digits (0-9), uses a total of O(n) space since it stores positions of each digit in the input number.
• The idx array is a fixed size of 10, thus O(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.