Skip to content

1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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;

    // From the back to the front, find the first num < nums[i + 1].
    int i;
    for (i = n - 2; i >= 0; --i)
      if (nums[i] < nums[i + 1])
        break;

    // From the back to the front, find the first num > nums[i] and swap it with nums[i].
    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]
    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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
  def getMinSwaps(self, num: str, k: int) -> int:
    def nextPermutation(nums: list[int]):
      n = len(nums)

      # From the back to the front, find the first num < nums[i + 1].
      i = n - 2
      while i >= 0:
        if nums[i] < nums[i + 1]:
          break
        i -= 1

      # From the back to the front, find the first num > nums[i] and swap it with nums[i].
      if i >= 0:
        for j in range(n - 1, i, -1):
          if nums[j] > nums[i]:
            nums[i], nums[j] = nums[j], nums[i]
            break

      def reverse(nums, l, r):
        while l < r:
          nums[l], nums[r] = nums[r], nums[l]
          l += 1
          r -= 1

      # Reverse nums[i + 1..n - 1]
      reverse(nums, i + 1, len(nums) - 1)

    A = [int(c) for c in num]  # Original
    B = A.copy()  # Permutated

    for _ in range(k):
      nextPermutation(B)

    def countSteps(A: list[int], B: list[int]) -> int:
      count = 0

      j = 0
      for i in range(len(A)):
        j = i
        while A[i] != B[j]:
          j += 1
        while i < j:
          B[j], B[j - 1] = B[j - 1], B[j]
          j -= 1
          count += 1

      return count

    return countSteps(A, B)