#60
Permutation Sequence
Hard Factorial number system
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The permutations of 1..n are listed in sorted order. Return the k-th one as a string.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k-th permutation of 1..n in sorted order, without listing them all.
Why this works: each choice of first digit covers (n-1)! permutations, so (k-1) / (n-1)! picks the first digit; repeat on the rest.
Example: n = 3, k = 3 (0-based 2)
2 / 2! = 1 → second of [1,2,3] → 2, k = 00 / 1! = 0 → 1, then 3"213"
✦Hints open one at a time
Generating all permutations is n! — far too many.
With n numbers, each choice of first digit covers (n−1)! permutations.
(k − 1) / (n − 1)! tells you which remaining number comes first.
↗Approach
Keep a list of unused numbers and use k − 1 (0-based). For each position, idx = k / fact(remaining − 1); take that number out of the list; k %= fact(remaining − 1).
</>Solution (Java)
import java.util.*;
class Solution {
public String getPermutation(int n, int k) {
List<Integer> nums = new ArrayList<>();
int[] fact = new int[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = fact[i - 1] * i;
nums.add(i);
}
k--; // 0-based
StringBuilder sb = new StringBuilder();
for (int left = n; left >= 1; left--) {
int idx = k / fact[left - 1]; // which block we're in
sb.append(nums.remove(idx));
k %= fact[left - 1];
}
return sb.toString();
}
}!Common mistake
Using 1-based k directly, which is off by one at block boundaries.
Complexity
- Time: O(n²) because of list removals (n ≤ 9).
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon