#1850
Minimum Adjacent Swaps to Reach the Kth Smallest Number
MediumTwo PointersStringGreedyTwo PointersGreedy
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n * k) |
| Space | O(n!) | O(n) |
💡
Intuition
Time O(n * k)Space O(n)
Instead of generating all permutations, we can find the k-th smallest wonderful integer directly using a more efficient approach. This involves finding the next permutation iteratively and counting the swaps needed to reach it.
⚙️
Algorithm
3 steps- 1Step 1: Find the next permutation of the string using a systematic approach.
- 2Step 2: Repeat the process k times to reach the k-th smallest wonderful integer.
- 3Step 3: Count the adjacent swaps needed to transform the original string into the k-th wonderful integer.
solution.py26 lines
1def next_permutation(s):
2 s = list(s)
3 n = len(s)
4 i = n - 2
5 while i >= 0 and s[i] >= s[i + 1]:
6 i -= 1
7 if i >= 0:
8 j = n - 1
9 while s[j] <= s[i]:
10 j -= 1
11 s[i], s[j] = s[j], s[i]
12 s[i + 1:] = reversed(s[i + 1:])
13 return ''.join(s)
14
15def min_adjacent_swaps(num, k):
16 current = num
17 for _ in range(k):
18 current = next_permutation(current)
19 swaps = 0
20 num_list = list(num)
21 for i in range(len(num_list)):
22 while num_list[i] != current[i]:
23 j = num_list.index(current[i], i)
24 num_list[i], num_list[j] = num_list[j], num_list[i]
25 swaps += 1
26 return swapsℹ
Complexity note: The time complexity is O(n * k) due to finding the next permutation k times, and space complexity is O(n) for storing the current permutation.
- 1Understanding permutations is crucial for this problem.
- 2Efficiently finding the next permutation can save time.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.