Minimum Adjacent Swaps to Reach the Kth Smallest Number

Problem Description

So, you think you can just rearrange numbers like they’re your socks? Well, think again! The problem at hand is to find the minimum number of adjacent swaps required to transform a given number into its Kth smallest permutation. Imagine you’re at a party, and you want to get to the front of the line for the buffet. You can only swap places with the person next to you. How many swaps will it take to get to the front? Spoiler alert: it’s not as easy as it sounds!

Code Solution


class Solution {
 public:
  int getMinSwaps(string num, int k) {
    string perm = num;

    while (k-- > 0)
      next_permutation(perm.begin(), perm.end());

    return countSteps(num, perm);
  }

 private:
  int countSteps(const string& A, string& B) {
    int count = 0;

    for (int i = 0, j = 0; i < A.length(); ++i) {
      j = i;
      while (A[i] != B[j])
        ++j;
      while (i < j) {
        swap(B[j], B[j - 1]);
        --j;
        ++count;
      }
    }

    return count;
  }
};

Approach

The approach here is as straightforward as a game of musical chairs. First, we generate the Kth permutation of the number using next_permutation. Then, we count how many adjacent swaps are needed to transform the original number into this permutation. It’s like figuring out how many times you need to elbow your way through the crowd to get to that delicious buffet!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N²)
Space Complexity	O(N)

Real-World Example

Imagine you’re at a concert, and you want to get closer to the stage. You can only swap places with the person next to you. If you’re currently in the 10th row and want to be in the 5th row, how many swaps will it take? This problem is a mathematical representation of that very scenario!