Permutation Sequence
Return the k-th permutation (1-indexed, lexicographic) of 1..n — without generating them all.
02
Intuition
Permutations starting with a fixed first digit form blocks of (n−1)! each. k ÷ (n−1)! says which digit leads; the remainder repeats the question one digit down. It's positional notation in the factorial number system.
03
Approach
1
Blocks of (n−1)!
With n=4, permutations come in 4 blocks of 3! = 6: those starting 1, then 2, … idx = (k−1) // 6 picks the leader from the unused digits.
2
Recurse on the remainder
k = (k−1) % (n−1)! + 1 and repeat with the remaining digits and (n−2)!, and so on down to one digit.
3
Zero-index to keep it clean
Working with k−1 throughout turns every step into plain divmod.
04
Solution & live demo
python
▶1class Solution:
▶2 def getPermutation(self, n, k):
▶3 from math import factorial
▶4 digits = [str(d) for d in range(1, n + 1)]
▶5 k -= 1
▶6 out = []
▶7 for i in range(n, 0, -1):
▶8 f = factorial(i - 1)
▶9 idx, k = divmod(k, f)
▶10 out.append(digits.pop(idx))
▶11 return "".join(out)
05
Edge cases
k = 1
Every divmod yields index 0 → smallest permutation 123…n.
k = n!
Always picks the last remaining digit → fully descending permutation.
06
Complexity
Time
O(n²)
Space
O(n)
n pops from a list; no permutation enumeration.