Skip to main content
Talentd

Minimum Adjacent Swaps to Reach the Kth Smallest Number - Solution & Explanation

MediumTwo PointersStringGreedy16 min readAsked at: Meta, Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: 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
Explanation: 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
Explanation: 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.

Approach Overview

Problem Overview: Given a numeric string num and an integer k, find the minimum number of adjacent swaps required to transform num into its kth next lexicographically smallest permutation. You first determine what the kth permutation looks like, then compute how many adjacent swaps are needed to reach it.

Approach 1: Using Next Permutation (O(k·n + n²) time, O(n) space)

Generate the target number by applying the next_permutation operation k times on the original string. This algorithm scans from right to left to find the first decreasing pair, swaps with the next larger digit, then reverses the suffix. Once the kth permutation is obtained, compute the minimum adjacent swaps needed to convert the original string into this target. Iterate through each position; when digits differ, search forward in the target and repeatedly swap left until the correct digit reaches the position. This simulates the minimum adjacent swaps required. The approach relies on string manipulation and a greedy bubble-style swap process.

Approach 2: Optimized Swap Calculation (O(k·n + n²) time, O(1) extra space)

After generating the kth permutation, compute swaps more efficiently using a greedy shifting strategy. Traverse both strings from left to right. If characters match, move forward. When they differ, locate the matching digit in the target suffix, then shift it left using adjacent swaps while counting operations. Each shift reduces the distance between the digit's current index and its desired position. This guarantees the minimal number of swaps because adjacent swaps preserve relative ordering. The logic combines ideas from greedy algorithms with pointer scanning similar to two pointers.

Recommended for interviews: Interviewers typically expect the next permutation approach combined with a greedy adjacent swap count. Showing the next_permutation logic demonstrates understanding of permutation generation, while the swap simulation shows how to compute minimal adjacent operations. The optimized swap counting variant is cleaner in implementation and easier to reason about during interviews.

Approach 1: Approach 1: Using Next Permutation

This approach involves finding the next permutation of the given number sequentially k times. Once we have the kth permutation, we compare it with the original number and calculate the minimum swaps needed to transform the original number into this new permutation.

This Python function first computes the kth permutation by finding the next permutation k times. The next_permutation function rearranges the list into the next lexicographically greater permutation. After obtaining the kth permutation, we calculate the minimum swaps needed to transform the original permutation into the kth one. This is achieved by finding the index of the element in the current list that matches the desired permutation and swapping it into the correct place.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * k), where n is the length of the string and k is the number of permutations to find.
Space Complexity: O(n), for storing the list representation of the numbers.

Try this approach in the editor →

Approach 2: Approach 2: Optimized Swap Calculation

This approach involves computing the kth permutation more efficiently using an algorithm to apply the minimum adjacent swaps directly based on the differences between current and target permutations. Instead of finding all permutations, this focuses on achieving the next permutations and dynamically swaps to approach the target.

This C++ implementation leverages the STL next_permutation to determine the kth permutation, then efficiently finds the number of adjacent swaps needed to reach this permutation. It does so by comparing the original and target permutations, only rearranging elements when necessary, and counting the swaps required for transformations.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n * k), where obtaining the next permutation takes O(n) for each of the k iterations.
Space Complexity: O(n), due to additional space needed for swap vectors or temporary strings.

Try this approach in the editor →

Approach 3: Find Next Permutation + Inversion Pairs

We can call the next_permutation function k times to get the kth smallest permutation s.

Next, we just need to calculate how many swaps are needed for num to become s.

Let's first consider a simple situation where all the digits in num are different. In this case, we can directly map the digit characters in num to indices. For example, if num is "54893" and s is "98345". We map each digit in num to an index, that is:

$ \begin{aligned} num[0] &= 5 &\rightarrow& \quad 0 \ num[1] &= 4 &\rightarrow& \quad 1 \ num[2] &= 8 &\rightarrow& \quad 2 \ num[3] &= 9 &\rightarrow& \quad 3 \ num[4] &= 3 &\rightarrow& \quad 4 \ \end{aligned}

Then, mapping each digit in s to an index results in "32410". In this way, the number of swaps needed to change num to s is equal to the number of inversion pairs in the index array after s is mapped.

If there are identical digits in num, we can use an array d to record the indices where each digit appears, where d[i] represents the list of indices where the digit i appears. To minimize the number of swaps, when mapping s to an index array, we only need to greedily select the index of the corresponding digit in d in order.

Finally, we can directly use a double loop to calculate the number of inversion pairs, or we can optimize it with a Binary Indexed Tree.

The time complexity is O(n times (k + n)), and the space complexity is O(n). Where n is the length of num$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Next Permutation

Time Complexity: O(n * k), where n is the length of the string and k is the number of permutations to find.
Space Complexity: O(n), for storing the list representation of the numbers.

Approach 2: Optimized Swap Calculation

Time Complexity: O(n * k), where obtaining the next permutation takes O(n) for each of the k iterations.
Space Complexity: O(n), due to additional space needed for swap vectors or temporary strings.

Find Next Permutation + Inversion Pairs—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Next Permutation + Swap SimulationO(k·n + n²)O(n)Most common solution; easy to implement and explain in interviews
Optimized Greedy Swap CalculationO(k·n + n²)O(1)When minimizing extra memory and implementing cleaner swap counting

Video Solution

Minimum Adjacent Swaps to Reach the Kth Smallest Number | LeetCode 1850 | Coders Camp • Coders Camp • 3,024 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Adjacent Swaps to Reach the Kth Smallest Number easy or hard?
The problem is classified as Medium because it combines two concepts: generating permutations and calculating minimal adjacent swaps. Each component is manageable individually, but implementing both correctly requires careful index handling and string manipulation.
Minimum Adjacent Swaps to Reach the Kth Smallest Number Python/Java solution
Python and Java implementations usually follow the same structure: compute the kth permutation using next permutation logic, then simulate adjacent swaps to transform the original number into that permutation. The algorithm works identically across languages including Python, Java, C++, and JavaScript.
How to solve Minimum Adjacent Swaps to Reach the Kth Smallest Number in O(n)?
A strict O(n) solution is not possible because generating the kth permutation itself requires repeated permutation operations. The practical optimal approach performs next permutation k times and then computes swap distance greedily. This results in O(k·n + n²) time, which is efficient for the constraints of the problem.
What is the best approach for Minimum Adjacent Swaps to Reach the Kth Smallest Number?
The most reliable method generates the kth smallest permutation using the next permutation algorithm, then counts the minimum adjacent swaps needed to convert the original string into that permutation. This combines permutation generation with a greedy swap simulation. Time complexity is O(k·n + n²) and space complexity is O(n).
Is Minimum Adjacent Swaps to Reach the Kth Smallest Number asked at Google/Amazon/Meta?
Permutation manipulation and minimum swap problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving next permutation, greedy swaps, and string transformations are common because they test algorithmic thinking and careful implementation.
What data structure is used in Minimum Adjacent Swaps to Reach the Kth Smallest Number?
The solution mainly uses arrays or strings to represent digits. Two-pointer scanning and greedy swapping are used to compute the minimal number of adjacent swaps. No advanced data structures are required beyond basic string or array manipulation.
What is the time complexity of Minimum Adjacent Swaps to Reach the Kth Smallest Number?
Generating the kth permutation requires applying the next permutation operation k times, which costs O(k·n). Counting the minimum adjacent swaps between the original and target permutation takes O(n²) in the worst case. Overall complexity is O(k·n + n²) with O(n) auxiliary space.

Ready to solve this problem?

Practice Minimum Adjacent Swaps to Reach the Kth Smallest Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Next Permutation