1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number LeetCode Solution
In this guide, you will get 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number LeetCode Solution with the best time and space complexity. The solution to Minimum Adjacent Swaps to Reach the Kth Smallest Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Adjacent Swaps to Reach the Kth Smallest Number solution in C++
- Minimum Adjacent Swaps to Reach the Kth Smallest Number solution in Java
- Minimum Adjacent Swaps to Reach the Kth Smallest Number solution in Python
- Additional Resources
Problem Statement of Minimum Adjacent Swaps to Reach the Kth Smallest Number
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.
Complexity Analysis
- Time Complexity:
- Space Complexity:
1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number LeetCode Solution in C++
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;
}
};
/* code provided by PROGIEZ */1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number LeetCode Solution in Java
class Solution {
public int getMinSwaps(String num, int k) {
int[] original = new int[num.length()];
for (int i = 0; i < original.length; ++i)
original[i] = num.charAt(i) - '0';
int[] permutated = original.clone();
for (int i = 0; i < k; ++i)
nextPermutation(permutated);
return countSteps(original, permutated);
}
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;
}
}
// code provided by PROGIEZ1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number LeetCode Solution in Python
class Solution:
def getMinSwaps(self, num: str, k: int) -> int:
original = [int(c) for c in num]
permutated = original.copy()
for _ in range(k):
self._nextPermutation(permutated)
return self._countSteps(original, permutated)
def _nextPermutation(self, 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)
def _countSteps(self, 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
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.