Minimum Adjacent Swaps to Reach the Kth Smallest Number

Med

#1690Time: O(k*N + N^2). Finding the target number takes O(k*N). The greedy swap calculation involves an outer loop of N iterations. Inside, finding the character and shifting elements (or using `List.remove`/`add`) takes O(N) time, leading to an O(N^2) complexity for the second part.Space: O(N), where N is the length of `num`. This space is used to store the character arrays or lists for the original and target numbers.

Patterns

Two Pointers Greedy

Data structures

String

Prompt

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 1^st smallest wonderful integer is "5489355214".
- The 2^nd smallest wonderful integer is "5489355241".
- The 3^rd smallest wonderful integer is "5489355412".
- The 4^th smallest wonderful integer is "5489355421".

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

The tests are generated in such a way that k^th 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first determines the target k-th smallest wonderful number by repeatedly applying the "next permutation" algorithm k times. Then, it calculates the minimum adjacent swaps required to transform the original number string into the target string. This is done by greedily placing the correct digit at each position from left to right, simulating the swaps and counting them.

Algorithm

Step 1: Find the k-th smallest wonderful number.
- A "wonderful number" is a permutation of the digits of num that is larger than num. The smallest wonderful number is the next lexicographical permutation.
- To find the k-th smallest, start with num and apply the standard next_permutation algorithm k times.
Step 2: Calculate minimum adjacent swaps via simulation.
- Convert the original num string to a mutable list of characters, originalList.
- The result from Step 1 is the target string.
- Initialize swaps = 0.
- Iterate from i = 0 to n-1 (where n is the number of digits):
  - If the character at originalList.get(i) does not match target[i], find the first index j > i where originalList.get(j) equals target[i].
  - Move the character from index j to i. This can be done by removing the character at j and inserting it at i.
  - This operation is equivalent to j - i adjacent swaps. Add this number to the total swaps count.
Step 3: Return total swaps.
- After the loop finishes, swaps will hold the minimum number of adjacent swaps required.

Walkthrough

The solution is broken down into two main parts:

Finding the Target Permutation: The problem defines a "wonderful" integer as a permutation of num's digits that is greater than num. The k-th smallest wonderful integer is simply the k-th lexicographically next permutation of num. We can find this by implementing the standard next_permutation algorithm and applying it k times to the digits of num.

1private void nextPermutation(char[] arr) {2    int n = arr.length;3    int i = n - 2;4    while (i >= 0 && arr[i] >= arr[i + 1]) {5        i--;6    }7    if (i >= 0) {8        int j = n - 1;9        while (arr[j] <= arr[i]) {10            j--;11        }12        swap(arr, i, j);13    }14    reverse(arr, i + 1, n - 1);15}16 17private void swap(char[] arr, int i, int j) { /* ... */ }18private void reverse(char[] arr, int start, int end) { /* ... */ }

Greedy Swap Calculation: Once we have the target string, say target, we need to find the minimum adjacent swaps to change num to target. A greedy approach works here. We iterate from left to right. For each position i, we ensure the correct character target[i] is placed there. We find the first occurrence of target[i] in our evolving string (starting from index i), say at index j, and then perform j-i adjacent swaps to move it to position i. We sum up these swaps. Using a List simplifies the removal and insertion of characters.

1public int getMinSwaps(String num, int k) {2    char[] targetArr = num.toCharArray();3    for (int i = 0; i < k; i++) {4        nextPermutation(targetArr);5    }6 7    List<Character> originalList = new ArrayList<>();8    for (char c : num.toCharArray()) {9        originalList.add(c);10    }11 12    int n = num.length();13    int swaps = 0;14    for (int i = 0; i < n; i++) {15        if (originalList.get(i) != targetArr[i]) {16            int j = i + 1;17            while (originalList.get(j) != targetArr[i]) {18                j++;19            }20            char charToMove = originalList.get(j);21            originalList.remove(j);22            originalList.add(i, charToMove);23            swaps += (j - i);24        }25    }26    return swaps;27}

Complexity

Time

O(k*N + N^2). Finding the target number takes O(k*N). The greedy swap calculation involves an outer loop of N iterations. Inside, finding the character and shifting elements (or using `List.remove`/`add`) takes O(N) time, leading to an O(N^2) complexity for the second part.

Space

O(N), where N is the length of `num`. This space is used to store the character arrays or lists for the original and target numbers.

Trade-offs

Pros

The logic is intuitive and directly simulates the process of swapping digits.
It's relatively easy to implement without requiring advanced data structures.

Cons

The O(N^2) complexity for calculating swaps can be inefficient for larger values of N (though it passes for the given constraints).
Repeatedly modifying a list by removing and inserting elements can be less performant than array-based manipulations, but conceptually simpler.

This more efficient approach also begins by finding the k-th smallest wonderful number. However, it calculates the minimum swaps using a more advanced technique. The problem is transformed into counting inversions in a permutation mapping. This mapping indicates the destination index for each digit from the original number. By using a Fenwick Tree (also known as a Binary Indexed Tree), we can count these inversions in O(N log N) time, which is faster than the O(N^2) simulation.

Algorithm

Step 1: Find the k-th smallest wonderful number.
- This step is identical to the previous approach. Apply the next_permutation algorithm k times to find the target string.
Step 2: Map original positions to target positions.
- The minimum number of adjacent swaps to transform a string A to its permutation B is the number of inversions in the mapping of element positions. To handle duplicate digits correctly, we must preserve their relative order.
- For each digit '0'-'9', create a queue of its indices in the target string.
- Create a permutation array P of size N. Iterate through the original num string from i = 0 to N-1. For each digit num[i], get its corresponding target position by dequeuing from the appropriate digit's queue. Store this position in P[i].
Step 3: Count inversions in P using a Fenwick Tree (BIT).
- An inversion in P is a pair (i, j) where i < j and P[i] > P[j].
- Initialize a Fenwick Tree of size N+1.
- Initialize inversions = 0.
- Iterate through P from i = 0 to N-1:
  - For each P[i], query the BIT to find how many numbers greater than P[i] have already been processed. This count is the number of new inversions involving P[i].
  - Add this count to inversions.
  - Update the BIT to mark P[i] as seen.
Step 4: Return total inversions.

Walkthrough

This method optimizes the calculation of swaps.

Finding the Target Permutation: Same as the first approach, taking O(k*N) time.

Calculating Swaps via Inversion Count: The key insight is that the minimum number of adjacent swaps required to transform one permutation into another is equal to the number of inversions in their position mapping. An inversion is a pair of elements that are in the wrong order relative to each other.

Constructing the Permutation Map P: We must map each character in num to its final position in target. To handle duplicates and ensure minimum swaps, the relative order of identical characters must be maintained (e.g., the first '5' in num maps to the first '5' in target). This mapping can be built in O(N) time using queues for each digit's target indices.
Counting Inversions with a Fenwick Tree: With the permutation map P, we count its inversions. A Fenwick Tree is perfect for this. We iterate through P, and for each element P[i], we query the tree for how many elements P[j] with j < i are greater than P[i]. This is an O(log N) operation. We then update the tree with P[i], also O(log N). Repeating for all N elements gives a total time of O(N log N).

1public int getMinSwaps(String num, int k) {2    char[] targetArr = num.toCharArray();3    for (int i = 0; i < k; i++) {4        nextPermutation(targetArr);5    }6    String target = new String(targetArr);7    int n = num.length();8 9    // Create mapping from original index to target index10    List<Integer>[] pos = new List[10];11    for (int i = 0; i < 10; i++) pos[i] = new ArrayList<>();12    for (int i = 0; i < n; i++) {13        pos[target.charAt(i) - '0'].add(i);14    }15 16    int[] p = new int[n];17    int[] indexCounters = new int[10];18    for (int i = 0; i < n; i++) {19        int digit = num.charAt(i) - '0';20        p[i] = pos[digit].get(indexCounters[digit]++);21    }22 23    // Count inversions in p using Fenwick Tree24    FenwickTree ft = new FenwickTree(n);25    int inversions = 0;26    for (int i = 0; i < n; i++) {27        inversions += ft.queryRange(p[i] + 2, n); // Count elements > p[i] already seen28        ft.update(p[i] + 1, 1); // Mark p[i] as seen29    }30    return inversions;31}32 33class FenwickTree {34    int[] bit;35    int size;36    FenwickTree(int n) {37        this.size = n + 1;38        this.bit = new int[this.size];39    }40    void update(int index, int val) { /* ... */ }41    int query(int index) { /* ... */ }42    int queryRange(int l, int r) {43        if (l > r) return 0;44        return query(r) - query(l - 1);45    }46}

Complexity

Time

O(k*N + N log N). Finding the target is O(k*N). Building the map `P` is O(N). Counting inversions with a Fenwick Tree is O(N log N). The overall complexity is determined by the larger of O(k*N) and O(N log N).

Space

O(N), where N is the length of `num`. Space is needed for the target string, position lists (`O(N)` total), the permutation map `P` (`O(N)`), and the Fenwick Tree (`O(N)`).

Trade-offs

Pros

Asymptotically more efficient for the swap calculation part (O(N log N) vs O(N^2)).
It is a standard and robust technique for problems involving permutation distance.

Cons

Requires knowledge of advanced data structures like Fenwick Trees.
The implementation is more complex than the direct simulation approach.

Solutions

Solution

1class Solution {2public3  int getMinSwaps(String num, int k) {4    char[] s = num.toCharArray();5    for (int i = 0; i < k; ++i) {6      nextPermutation(s);7    }8    List<Integer>[] d = new List[10];9    Arrays.setAll(d, i->new ArrayList<>());10    int n = s.length;11    for (int i = 0; i < n; ++i) {12      d[num.charAt(i) - '0'].add(i);13    }14    int[] idx = new int[10];15    int[] arr = new int[n];16    for (int i = 0; i < n; ++i) {17      arr[i] = d[s[i] - '0'].get(idx[s[i] - '0']++);18    }19    int ans = 0;20    for (int i = 0; i < n; ++i) {21      for (int j = 0; j < i; ++j) {22        if (arr[j] > arr[i]) {23          ++ans;24        }25      }26    }27    return ans;28  }29private30  boolean nextPermutation(char[] nums) {31    int n = nums.length;32    int i = n - 2;33    while (i >= 0 && nums[i] >= nums[i + 1]) {34      --i;35    }36    if (i < 0) {37      return false;38    }39    int j = n - 1;40    while (j >= 0 && nums[i] >= nums[j]) {41      --j;42    }43    swap(nums, i++, j);44    for (j = n - 1; i < j; ++i, --j) {45      swap(nums, i, j);46    }47    return true;48  }49private50  void swap(char[] nums, int i, int j) {51    char t = nums[i];52    nums[i] = nums[j];53    nums[j] = t;54  }55}

1class Solution {2public:3  int getMinSwaps(string num, int k) {4    string s = num;5    for (int i = 0; i < k; ++i) {6      next_permutation(begin(s), end(num));7    }8    vector<int> d[10];9    int n = num.size();10    for (int i = 0; i < n; ++i) {11      d[num[i] - '0'].push_back(i);12    }13    int idx[10]{};14    vector<int> arr(n);15    for (int i = 0; i < n; ++i) {16      arr[i] = d[s[i] - '0'][idx[s[i] - '0']++];17    }18    int ans = 0;19    for (int i = 0; i < n; ++i) {20      for (int j = 0; j < i; ++j) {21        if (arr[j] > arr[i]) {22          ++ans;23        }24      }25    }26    return ans;27  }28};

1class Solution:2    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))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem