#1850

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Minimum Adjacent Swaps to Reach the Kth Smallest Number

Find the minimum number of adjacent swaps to reach the kth smallest wonderful integer from a given number string.

Problem Statement

You are given a string num, representing a large integer, and an integer k. You are tasked with determining the minimum number of adjacent swaps required to rearrange the digits of num to reach the kth smallest wonderful number. A wonderful number is defined as a permutation of the digits in num that is greater in value than num. There can be many such permutations, but only the smallest ones matter.

Your goal is to return the minimum number of adjacent digit swaps needed to transform num into the kth smallest wonderful number. Keep in mind that the number of possible permutations grows rapidly, so finding an efficient way to calculate the kth permutation and determining how to swap the digits efficiently is key to solving the problem.

Examples

Example 1

Input: num = "5489355142", k = 4

Output: 2

The 4th smallest wonderful number is "5489355421". To get this number:

Swap index 7 with index 8: "5489355142" -> "5489355412"
Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2

Input: num = "11112", k = 4

Output: 4

The 4th smallest wonderful number is "21111". To get this number:

Swap index 3 with index 4: "11112" -> "11121"
Swap index 2 with index 3: "11121" -> "11211"
Swap index 1 with index 2: "11211" -> "12111"
Swap index 0 with index 1: "12111" -> "21111"

Example 3

Input: num = "00123", k = 1

Output: 1

The 1st smallest wonderful number is "00132". To get this number:

Swap index 3 with index 4: "00123" -> "00132"

Constraints

2 <= num.length <= 1000
1 <= k <= 1000
num only consists of digits.

Solution Approach

Two-Pointer Scanning

The key to solving this problem is efficiently finding the next permutation of the number k times. By using a two-pointer technique, we can find and swap the digits to move toward the desired permutation. After finding each next permutation, the pointer helps identify the minimum adjacent swaps needed.

Greedy Approach

A greedy approach can be used to minimize the number of swaps by selecting the smallest possible permutation in each step. This minimizes the number of adjacent swaps while ensuring that the desired permutation is reached efficiently.

Tracking Invariants

We can track the current state of the number as we make swaps, ensuring that each step moves closer to the kth smallest permutation. By tracking the state efficiently, we avoid unnecessary recalculations and focus on advancing the number to the correct position.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used to find the next permutation and the number of swaps required. In the worst case, finding the next permutation and performing swaps takes O(n), where n is the length of the number string. Given that we perform this operation k times, the time complexity is approximately O(k * n). The space complexity depends on the method chosen for tracking permutations, but it generally remains O(n) for storing the digits and their indices.

What Interviewers Usually Probe

Can the candidate identify the next permutation and apply it repeatedly?
Does the candidate understand the trade-offs between different strategies to minimize swaps?
Is the candidate able to optimize the process for finding the kth smallest permutation?

Common Pitfalls or Variants

Common pitfalls

Not using the two-pointer technique efficiently, leading to unnecessary swaps.
Failing to account for edge cases where the number contains repeated digits or leading zeros.
Overcomplicating the problem by using a brute-force approach to generate permutations.

Follow-up variants

What if we had to find the mth smallest permutation instead of the kth?
What if the input number is extremely large, pushing the upper limit of constraints?
What if the digits were not confined to 0-9 but included other characters or symbols?

FAQ

What is the best approach to solving the Minimum Adjacent Swaps to Reach the Kth Smallest Number problem?

A two-pointer scanning approach combined with greedy techniques is the most efficient way to solve this problem.

How do we ensure that we are minimizing the number of swaps?

By using a greedy algorithm and tracking the next permutation, we minimize the swaps needed at each step.

How does GhostInterview help with solving this problem?

GhostInterview guides you through understanding and applying the two-pointer method to solve the problem optimally.

Can this problem be solved without using the two-pointer technique?

While it can be solved using brute force, the two-pointer technique provides a more efficient solution.

What is a wonderful number in the context of this problem?

A wonderful number is any permutation of the digits in num that is greater than num itself, and we seek the kth smallest such permutation.

terminal

Solution

Solution 1: Find Next Permutation + Inversion Pairs

We can call the `next_permutation` function $k$ times to get the $k$th smallest permutation $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        def next_permutation(nums: List[str]) -> bool:
            n = len(nums)
            i = n - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1
            if i < 0:
                return False
            j = n - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
            nums[i + 1 : n] = nums[i + 1 : n][::-1]
            return True

        s = list(num)
        for _ in range(k):
            next_permutation(s)
        d = [[] for _ in range(10)]
        idx = [0] * 10
        n = len(s)
        for i, c in enumerate(num):
            j = ord(c) - ord("0")
            d[j].append(i)
        arr = [0] * n
        for i, c in enumerate(s):
            j = ord(c) - ord("0")
            arr[i] = d[j][idx[j]]
            idx[j] += 1
        return sum(arr[j] > arr[i] for i in range(n) for j in range(i))

Continue Practicing

#1754 largest merge of two strings #1963 minimum number of swaps to make the string balanced #2193 minimum number of moves to make palindrome