Minimum Adjacent Swaps to Reach the Kth Smallest Number

You are given a string num representing a large integer and an integer k. A number is called wonderful if it is a permutation of num that is greater than num. Return the minimum number of adjacent swaps needed to reach the kth smallest wonderful number.

This is LeetCode 1850: Minimum Adjacent Swaps to Reach the Kth Smallest Number, a medium problem that combines two classic techniques: generating the next permutation and counting minimum adjacent swaps to transform one sequence into another. Once you break it into those two phases, each one is clean and well-understood.

Why this problem matters

This problem tests whether you can decompose a compound task into independent subproblems. Phase one (finding the target permutation) is a direct application of the next permutation algorithm. Phase two (counting minimum swaps) is a greedy simulation. Neither phase is difficult on its own, but recognizing the decomposition under time pressure is the real skill.

The next permutation subroutine appears in dozens of other problems. The greedy swap counting technique shows up whenever you need to transform one arrangement into another using only adjacent swaps. Practicing this problem drills both skills.

The brute force approach

You could generate all permutations of num in sorted order, find the kth one larger than num, and then try all possible swap sequences. This is completely impractical. The number of permutations grows factorially, and finding the optimal swap sequence adds another layer of complexity.

A better brute force applies the next permutation algorithm k times to find the target, then tries all possible orderings of swaps. But even this is too slow because finding the optimal swap ordering is itself expensive without the right insight.

from itertools import permutations

def brute_force(num, k):
    perms = sorted(set(permutations(num)))
    idx = perms.index(tuple(num))
    target = perms[idx + k]
    # ... still need to count minimum swaps

The key realization is that you do not need to search for the optimal swap order. A greedy left-to-right matching strategy always produces the minimum number of adjacent swaps.

The key insight: two independent phases

The problem splits cleanly into two tasks:

1. Find the target. Apply the next permutation algorithm k times to num. This gives you the kth smallest wonderful number.
2. Count swaps. Given the original num and the target, count the minimum number of adjacent swaps to transform one into the other.

For phase two, the greedy strategy is: process positions left to right. For each position, find the matching character in the remaining portion of the current array, then bubble it into place using adjacent swaps. This is optimal because moving a character into its correct position from left to right never creates unnecessary work for later positions.

Walking through it step by step

Let's trace through num = "54893", k = 4. We apply next permutation 4 times to find the target, then count adjacent swaps to get there.

The answer is 4 adjacent swaps. Each step greedily places the correct character at the next position by bubbling it leftward. No backtracking is needed because earlier positions are already finalized.

The solution

def getMinSwaps(num: str, k: int) -> int:
    target = list(num)

    # Phase 1: apply next permutation k times
    for _ in range(k):
        next_permutation(target)

    # Phase 2: count minimum adjacent swaps
    original = list(num)
    swaps = 0

    for i in range(len(original)):
        if original[i] != target[i]:
            # Find matching character
            j = i + 1
            while original[j] != target[i]:
                j += 1
            # Bubble it into position
            while j > i:
                original[j], original[j - 1] = original[j - 1], original[j]
                j -= 1
                swaps += 1

    return swaps


def next_permutation(arr: list[str]) -> None:
    n = len(arr)
    i = n - 2

    # Find pivot: rightmost index where arr[i] < arr[i+1]
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1

    if i >= 0:
        # Find successor: smallest element in suffix larger than arr[i]
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]

    # Reverse the suffix
    left, right = i + 1, n - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

Phase 1 uses the standard next permutation algorithm. Find the pivot (rightmost digit that can be increased), swap it with the smallest larger digit in the suffix, and reverse the suffix to minimize it. Repeat this k times.

Phase 2 processes positions left to right. When the character at position i does not match the target, it scans right to find the first matching character and swaps it leftward one position at a time. Each adjacent swap brings the character one step closer. Once the character reaches its target position, we move to the next index.

Why greedy swap counting works

When you process positions left to right and bubble each target character into place, you never undo previous work. Characters already placed at positions 0 through i - 1 are exactly correct and are not moved again. This is because the search for the matching character starts at index i + 1, so it never touches the already-fixed prefix.

The greedy approach gives the minimum swap count because adjacent swaps have a direct relationship to inversions. The number of adjacent swaps needed to transform one permutation into another equals the number of inversions between them. Processing left to right and always choosing the nearest matching character minimizes the total inversion count.

Complexity analysis

Phase 1 runs next permutation k times, each taking O(n) time. Phase 2 scans and swaps in a nested loop that is O(n^2) in the worst case. Since k can be up to 1000 and n up to 1000, both phases are comfortably within limits.

Building blocks

This problem is built from two reusable patterns that CodeBricks drills independently.

1. Next permutation

The three-step algorithm for generating the lexicographically next permutation: find the pivot, swap the successor, reverse the suffix. This is the same algorithm from LeetCode 31, and it appears as a subroutine in many permutation-related problems. You need to be able to write it from memory without hesitation.

2. Greedy adjacent swap counting

The pattern of transforming one sequence into another by processing positions left to right and bubbling each element into place:

swaps = 0
for i in range(n):
    if current[i] != target[i]:
        j = i + 1
        while current[j] != target[i]:
            j += 1
        while j > i:
            current[j], current[j - 1] = current[j - 1], current[j]
            j -= 1
            swaps += 1

This greedy strategy works whenever the target is a permutation of the current sequence and you are limited to adjacent swaps. The same approach applies to problems about sorting with adjacent swaps, minimum swaps to sort an array, and string transformation problems.

Edge cases

Before submitting, make sure your solution handles these:

• k = 1: the target is just the next permutation. Only one application of the next permutation algorithm is needed.
• All digits the same like "1111": no wonderful number exists. The constraints guarantee a valid answer, but it is worth noting that next permutation on a non-decreasing sequence produces the same sequence.
• Already nearly the target: if the original and target differ in only the last two positions, only one swap is needed.
• Large k with small n: the target could wrap through many permutations. The next permutation algorithm handles this correctly since each call produces the immediate next permutation regardless of how many have been generated.
• Repeated digits: the next permutation algorithm uses >= in the pivot scan to correctly handle duplicates. The swap counting phase also handles duplicates naturally since it searches for the first matching character, not a unique one.

From understanding to recall

You understand the two-phase approach: find the target with next permutation, then count swaps greedily. But can you write both phases from scratch in an interview without looking at the code?

The next permutation algorithm has three steps that must be executed in the right order with the right comparison operators. The swap counting loop has a nested structure where the inner while loop bubbles a character into position. These details are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the next permutation subroutine and the greedy swap counting loop independently. After a few rounds, both patterns are automatic. You see "transform to kth permutation with minimum swaps" and the code flows out without hesitation.

Related posts

• Next Permutation - The three-step algorithm used as a subroutine in phase one. Mastering this is a prerequisite for solving the current problem efficiently.
• Minimum Number of Swaps to Make the String Balanced - Another problem where greedy swap counting produces the optimal answer.
• Permutations II - Generating permutations with duplicate handling, which connects to why next permutation correctly skips duplicates.

CodeBricks breaks LeetCode 1850 into its next permutation and greedy swap counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a permutation-and-swap question shows up in your interview, you do not think about it. You just write it.