Minimum Adjacent Swaps to Reach the Kth Smallest Number

Minimum Adjacent Swaps to Reach the Kth Smallest Number - Problem

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

For example, when num = "5489355142":

The 1st smallest wonderful integer is "5489355214".
The 2nd smallest wonderful integer is "5489355241".
The 3rd smallest wonderful integer is "5489355412".
The 4th smallest wonderful integer is "5489355421".

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the kth smallest wonderful integer.

The tests are generated in such a way that kth smallest wonderful integer exists.

Input & Output

Example 1 — Basic Case

$ Input: num = "5489355142", k = 4

› Output: 2

💡 Note: The 4th smallest wonderful number is "5489355421". We need 2 adjacent swaps to transform "5489355142" to "5489355421": swap positions 7-8 (4↔2) then swap positions 8-9 (4↔1).

Example 2 — Small Input

$ Input: num = "11112", k = 1

› Output: 4

💡 Note: The 1st smallest wonderful number is "11121". We need 4 adjacent swaps to move the '2' from position 4 to position 3: swap 4 times to get "11121".

Example 3 — Multiple Steps

$ Input: num = "123", k = 2

› Output: 3

💡 Note: The permutations greater than "123" are ["132", "213", "231", "312", "321"]. The 2nd smallest is "213". From "123" → "132" (1 swap) → "213" (2 more swaps) = 3 total swaps.

Constraints

1 ≤ num.length ≤ 1000
1 ≤ k ≤ 1000
num consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

Original number string and target k-th wonderful permutation

Transform

Apply next permutation algorithm k times

Count Swaps

Calculate total adjacent swaps needed for transformation

Key Takeaway

🎯 Key Insight: Use next permutation algorithm repeatedly instead of generating all permutations

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use the next permutation algorithm repeatedly to find the k-th wonderful number, then calculate adjacent swaps needed. The greedy approach applies next permutation k times with O(k × n²) time complexity, which is much better than generating all permutations.

Common Approaches

Approach	Time	Space	Notes
✓ Next Permutation Algorithm	O(k × n²)	O(1)	Use next permutation algorithm k times and count adjacent swaps efficiently
Generate All Permutations	O(n! × n)	O(n! × n)	Generate all permutations, sort them, find the k-th one, then calculate swaps

Next Permutation Algorithm — Algorithm Steps

Start with original number
Apply next permutation algorithm k times
For each transformation, count adjacent swaps needed
Return total number of swaps

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Pivot

Find rightmost character smaller than its next

Find Successor

Find smallest character to right that's larger than pivot

Swap & Reverse

Swap pivot with successor, reverse suffix

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void reverse(char* arr, int start, int end) {
    while (start < end) {
        char temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

int nextPermutation(char* s) {
    int len = strlen(s);
    int i = len - 2;
    
    while (i >= 0 && s[i] >= s[i + 1]) {
        i--;
    }
    
    if (i == -1) {
        return 0;
    }
    
    int j = len - 1;
    while (s[j] <= s[i]) {
        j--;
    }
    
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
    
    reverse(s, i + 1, len - 1);
    return 1;
}

int countAdjacentSwaps(char* s1, char* s2) {
    int n = strlen(s1);
    char* arr = malloc((n + 1) * sizeof(char));
    strcpy(arr, s1);
    int swaps = 0;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] != s2[i]) {
            int j = i + 1;
            while (j < n && arr[j] != s2[i]) {
                j++;
            }
            while (j > i) {
                char temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                swaps++;
                j--;
            }
        }
    }
    free(arr);
    return swaps;
}

int solution(char* num, int k) {
    int len = strlen(num);
    char* current = malloc((len + 1) * sizeof(char));
    strcpy(current, num);
    int totalSwaps = 0;
    
    for (int i = 0; i < k; i++) {
        char* prev = malloc((len + 1) * sizeof(char));
        strcpy(prev, current);
        if (!nextPermutation(current)) {
            free(prev);
            free(current);
            return -1;
        }
        totalSwaps += countAdjacentSwaps(prev, current);
        free(prev);
    }
    
    free(current);
    return totalSwaps;
}

int main() {
    char num[20];
    int k;
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    scanf("%d", &k);
    printf("%d\n", solution(num, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n²)

Apply next permutation k times, each taking O(n), plus O(n²) for counting swaps

⚠ Quadratic Growth

Space Complexity

O(1)

Only use constant extra space for variables

✓ Linear Space

12.0K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Next Permutation Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler