K-th Permutation
Hard · rating 1850 · Combinatorics, Math
The first line has n. The second line has k (1-indexed). Print the k-th permutation of 1, 2, …, n in lexicographic order, space-separated. k does not exceed n!.
Constraints: 1 ≤ n ≤ 9
Editorial
Approach
Work in the factorial number system. With n items, the first element is fixed by k / (n-1)! — each choice of first element accounts for (n-1)! permutations. Pick that element, take k mod (n-1)!, and recurse on the remaining items.
Key detail
Convert k to 0-indexed first. Removing the chosen element from the candidate list keeps the remaining ones in sorted order for the next digit.
k -= 1
for i in range(n, 0, -1):
idx = k // fact[i-1]; k %= fact[i-1]
out.append(nums.pop(idx))Complexity
Time: O(n²) from the list removals. Space: O(n).
Related problems
- Pascal's Triangle Row — Medium
- Balanced Bracket Count — Hard
- Dice Sum Ways — Medium
- Nth Prime — Hard
- Unique Grid Paths — Hard
- Add Binary Strings — Medium