LeetCode 1850 - Minimum Adjacent Swaps to Reach the Kth Smallest Number

LeetCode Problem 1850

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Greedy

Solution

Problem Understanding

The problem asks us to compute the minimum number of adjacent swaps needed to transform a given number num into the kth smallest wonderful integer. A wonderful integer is any permutation of num's digits that is strictly greater than num. Among all such permutations, we only care about the kth smallest one.

The input consists of a string num, representing a potentially very large integer, and an integer k, which indicates the position of the target permutation in the ascending order of all wonderful numbers. The output is a single integer representing the minimal number of swaps of adjacent digits to transform the original num into this target permutation.

Constraints are:

• num has length between 2 and 1000, so solutions need to handle moderately large strings efficiently.
• k is up to 1000, which implies we cannot generate all permutations explicitly, but we only need to perform up to k iterations of next-permutation logic.
• The input consists only of digits, so no need to handle non-digit characters.

Edge cases to consider include numbers with repeated digits, numbers with leading zeros, and cases where k = 1 (the first next permutation). The problem guarantees that the kth smallest wonderful integer exists, so we do not need to handle cases where there are fewer than k permutations.

Approaches

The brute-force approach would involve generating all permutations of num that are greater than num, sorting them, and selecting the kth smallest one. Then, we would compute the minimum number of adjacent swaps to convert num into that target permutation by simulating bubble-sort style swaps. While correct, this approach is infeasible because the number of permutations grows factorially with the length of num.

The key insight for an optimal approach is twofold: first, we can compute the next permutation iteratively k times to get the kth smallest wonderful number without generating all permutations. Second, once we have the target permutation, we can calculate the minimum adjacent swaps by greedily moving each digit in the original number to its position in the target number, counting each adjacent swap.

This reduces the problem from factorial complexity to O(k * n + n^2) complexity, where n is the length of num and k is the number of next permutations we need.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * n)	O(n!)	Generates all permutations, sorts, and counts swaps
Optimal	O(k * n + n^2)	O(n)	Uses k next-permutation steps and greedy adjacent swaps

Algorithm Walkthrough

1. Convert num into a list of characters for mutability.
2. Apply the next permutation algorithm k times. This algorithm works by scanning from the end of the list to find the first decreasing element, swapping it with the next larger element, and reversing the suffix. After k iterations, we have the kth smallest wonderful number.
3. Initialize a counter swaps to 0. This will track the number of adjacent swaps needed.
4. Iterate through each index i of the original number. For each index:

• If the digit at index i matches the digit in the target, continue.
• Otherwise, find the position j in the original list where the target digit is located.
• Move the digit at position j to position i by performing j - i adjacent swaps, incrementing swaps accordingly, and update the list.

5. After processing all digits, return swaps as the minimum number of adjacent swaps.

Why it works: The next-permutation algorithm ensures we get the exact kth smallest permutation. The greedy adjacent swap approach guarantees the minimal number of swaps because each swap moves the target digit one step closer to its final position without unnecessary moves.

Python Solution

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        # Step 1: Convert to list for mutability
        num_list = list(num)
        target_list = list(num)
        
        # Step 2: Compute kth next permutation
        for _ in range(k):
            i = len(target_list) - 2
            while i >= 0 and target_list[i] >= target_list[i + 1]:
                i -= 1
            if i >= 0:
                j = len(target_list) - 1
                while target_list[j] <= target_list[i]:
                    j -= 1
                target_list[i], target_list[j] = target_list[j], target_list[i]
            target_list[i+1:] = reversed(target_list[i+1:])
        
        # Step 3: Count minimum adjacent swaps
        swaps = 0
        num_list_copy = num_list.copy()
        for i in range(len(num_list)):
            if num_list_copy[i] != target_list[i]:
                j = i
                while num_list_copy[j] != target_list[i]:
                    j += 1
                while j > i:
                    num_list_copy[j], num_list_copy[j-1] = num_list_copy[j-1], num_list_copy[j]
                    swaps += 1
                    j -= 1
        return swaps

Explanation: We first generate the kth smallest wonderful number using the next-permutation technique. Then, we iterate through the original number and greedily move each digit to match the target by counting the minimal adjacent swaps. Each inner loop executes at most n swaps per digit, leading to O(n^2) complexity for the swaps calculation.

Go Solution

func getMinSwaps(num string, k int) int {
    numList := []byte(num)
    targetList := []byte(num)

    // Compute kth next permutation
    for t := 0; t < k; t++ {
        i := len(targetList) - 2
        for i >= 0 && targetList[i] >= targetList[i+1] {
            i--
        }
        if i >= 0 {
            j := len(targetList) - 1
            for targetList[j] <= targetList[i] {
                j--
            }
            targetList[i], targetList[j] = targetList[j], targetList[i]
        }
        left, right := i+1, len(targetList)-1
        for left < right {
            targetList[left], targetList[right] = targetList[right], targetList[left]
            left++
            right--
        }
    }

    // Count minimum adjacent swaps
    swaps := 0
    numCopy := append([]byte{}, numList...)
    for i := 0; i < len(numList); i++ {
        if numCopy[i] != targetList[i] {
            j := i
            for numCopy[j] != targetList[i] {
                j++
            }
            for j > i {
                numCopy[j], numCopy[j-1] = numCopy[j-1], numCopy[j]
                swaps++
                j--
            }
        }
    }
    return swaps
}

Explanation: The Go solution mirrors the Python solution. We use []byte slices for mutability and a similar nested loop structure to compute adjacent swaps. Go requires careful slice handling, which is done using append to copy the original slice.

Worked Examples

Example 1: num = "5489355142", k = 4

1. Next permutation steps:

• 1st: "5489355214"
• 2nd: "5489355241"
• 3rd: "5489355412"
• 4th: "5489355421"

2. Counting swaps:

• Index 7: move '4' from index 8 → swaps = 1
• Index 8: move '2' from index 9 → swaps = 2

3. Output: 2

Example 2: num = "11112", k = 4

1. Next permutations:

• 1st: "11121"
• 2nd: "11211"
• 3rd: "12111"
• 4th: "21111"

2. Counting swaps: 4 adjacent swaps move '2' to the front.
3. Output: 4

Example 3: num = "00123", k = 1

1. Next permutation: "00132"
2. Counting swaps: swap '3' and '2' → swaps = 1
3. Output: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k * n + n^2)	k iterations for next permutation, n^2 for adjacent swaps computation
Space	O(n)	We store mutable copies of num and target permutations

The n^2 component dominates for large n when k is small; for k up to 1000, this is acceptable.

Test Cases

# Provided examples
assert Solution().getMinSwaps("5489355142", 4) == 2  # 4th smallest wonderful number
assert Solution().getMinSwaps("11112", 4) == 4        # repeated digits
assert Solution().getMinSwaps("00123", 1) == 1        # leading zeros

# Edge cases
assert Solution().get