Minimum Adjacent Swaps to Reach the Kth Smallest Number

Problem Description

Ah, the classic dilemma of wanting to rearrange your life (or in this case, a number) with the least amount of effort. 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 snack table (because who doesn’t love snacks?), but you can only shuffle your way through the crowd one person at a time.

In simpler terms, given a number represented as a string and an integer K, you need to figure out how many times you need to swap adjacent digits to get to the Kth smallest permutation of that number.

Code Solution


class Solution {
  public int getMinSwaps(String num, int k) {
    int[] A = new int[num.length()]; // Original

    for (int i = 0; i < A.length; ++i)
      A[i] = num.charAt(i) - '0';

    int[] B = A.clone(); // Permutated

    for (int i = 0; i < k; ++i)
      nextPermutation(B);

    return countSteps(A, B);
  }

  public void nextPermutation(int[] nums) {
    final int n = nums.length;

    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    if (i >= 0)
      for (int j = n - 1; j > i; --j)
        if (nums[j] > nums[i]) {
          swap(nums, i, j);
          break;
        }

    reverse(nums, i + 1, n - 1);
  }

  private void reverse(int[] nums, int l, int r) {
    while (l < r)
      swap(nums, l++, r--);
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  private int countSteps(int[] A, int[] 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, j - 1);
        --j;
        ++count;
      }
    }

    return count;
  }
}

Approach Explanation

The code starts by converting the input string into an integer array for easier manipulation. It then generates the Kth permutation of the number using the nextPermutation method. After obtaining the desired permutation, it counts the number of adjacent swaps needed to transform the original array into this new permutation using the countSteps method.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²) in the worst case, where n is the length of the number.
Space Complexity	O(n) for storing the integer arrays.

Real-World Example

Imagine you’re at a concert, and you want to get to the front row to see your favorite band. You can only move one person at a time, and you want to get there as quickly as possible. Each swap represents a move to get closer to the front. The Kth smallest permutation is like the perfect spot in the front row where you can see everything without any obstructions.