# Minimum Adjacent Swaps to Reach the Kth Smallest Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number)
Canonical: https://scaleengineer.com/dsa/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## 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.

**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
## Greedy Swapping Simulation
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.
**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.
**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.
### Explanation
The solution is broken down into two main parts:

1.  **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`.

    ```java
    private void nextPermutation(char[] arr) {
        int n = arr.length;
        int i = n - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            while (arr[j] <= arr[i]) {
                j--;
            }
            swap(arr, i, j);
        }
        reverse(arr, i + 1, n - 1);
    }

    private void swap(char[] arr, int i, int j) { /* ... */ }
    private void reverse(char[] arr, int start, int end) { /* ... */ }
    ```

2.  **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.

    ```java
    public int getMinSwaps(String num, int k) {
        char[] targetArr = num.toCharArray();
        for (int i = 0; i < k; i++) {
            nextPermutation(targetArr);
        }

        List<Character> originalList = new ArrayList<>();
        for (char c : num.toCharArray()) {
            originalList.add(c);
        }

        int n = num.length();
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            if (originalList.get(i) != targetArr[i]) {
                int j = i + 1;
                while (originalList.get(j) != targetArr[i]) {
                    j++;
                }
                char charToMove = originalList.get(j);
                originalList.remove(j);
                originalList.add(i, charToMove);
                swaps += (j - i);
            }
        }
        return swaps;
    }
    ```
### 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.

## Inversion Count with Fenwick Tree
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.
**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)`).
**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.
### Explanation
This method optimizes the calculation of swaps.

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

2.  **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)`.

    ```java
    public int getMinSwaps(String num, int k) {
        char[] targetArr = num.toCharArray();
        for (int i = 0; i < k; i++) {
            nextPermutation(targetArr);
        }
        String target = new String(targetArr);
        int n = num.length();

        // Create mapping from original index to target index
        List<Integer>[] pos = new List[10];
        for (int i = 0; i < 10; i++) pos[i] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            pos[target.charAt(i) - '0'].add(i);
        }

        int[] p = new int[n];
        int[] indexCounters = new int[10];
        for (int i = 0; i < n; i++) {
            int digit = num.charAt(i) - '0';
            p[i] = pos[digit].get(indexCounters[digit]++);
        }

        // Count inversions in p using Fenwick Tree
        FenwickTree ft = new FenwickTree(n);
        int inversions = 0;
        for (int i = 0; i < n; i++) {
            inversions += ft.queryRange(p[i] + 2, n); // Count elements > p[i] already seen
            ft.update(p[i] + 1, 1); // Mark p[i] as seen
        }
        return inversions;
    }

    class FenwickTree {
        int[] bit;
        int size;
        FenwickTree(int n) {
            this.size = n + 1;
            this.bit = new int[this.size];
        }
        void update(int index, int val) { /* ... */ }
        int query(int index) { /* ... */ }
        int queryRange(int l, int r) {
            if (l > r) return 0;
            return query(r) - query(l - 1);
        }
    }
    ```
### 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.**

# Solutions
### Java

```java
class Solution {
public
  int getMinSwaps(String num, int k) {
    char[] s = num.toCharArray();
    for (int i = 0; i < k; ++i) {
      nextPermutation(s);
    }
    List<Integer>[] d = new List[10];
    Arrays.setAll(d, i->new ArrayList<>());
    int n = s.length;
    for (int i = 0; i < n; ++i) {
      d[num.charAt(i) - '0'].add(i);
    }
    int[] idx = new int[10];
    int[] arr = new int[n];
    for (int i = 0; i < n; ++i) {
      arr[i] = d[s[i] - '0'].get(idx[s[i] - '0']++);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[j] > arr[i]) {
          ++ans;
        }
      }
    }
    return ans;
  }
private
  boolean nextPermutation(char[] nums) {
    int n = nums.length;
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      --i;
    }
    if (i < 0) {
      return false;
    }
    int j = n - 1;
    while (j >= 0 && nums[i] >= nums[j]) {
      --j;
    }
    swap(nums, i++, j);
    for (j = n - 1; i < j; ++i, --j) {
      swap(nums, i, j);
    }
    return true;
  }
private
  void swap(char[] nums, int i, int j) {
    char t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getMinSwaps(string num, int k) {
    string s = num;
    for (int i = 0; i < k; ++i) {
      next_permutation(begin(s), end(num));
    }
    vector<int> d[10];
    int n = num.size();
    for (int i = 0; i < n; ++i) {
      d[num[i] - '0'].push_back(i);
    }
    int idx[10]{};
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = d[s[i] - '0'][idx[s[i] - '0']++];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[j] > arr[i]) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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))

```