Permutation Sequence

Permutation Sequence

What is this problem about?

The Permutation Sequence problem asks for the k-th permutation of numbers 1..n in lexicographic order, without generating all permutations. This hard coding problem uses a factoradic (factorial number system) approach to directly construct the k-th permutation in O(n²) time. The math and recursion interview pattern is the core.

Why is this asked in interviews?

Jump Trading, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because generating all permutations (n!) is infeasible for large n, but the factoradic method directly computes the answer in O(n²) — demonstrating mathematical insight over brute force.

Algorithmic pattern used

Factoradic decomposition. With n numbers, there are (n-1)! permutations starting with each digit. Adjust k to 0-indexed: k -= 1. For each position i from n down to 1: digit_index = k // (i-1)!. Pick available[digit_index] as the next digit. Remove it from available. Update k = k % (i-1)!.

Example explanation

n=3, k=3. Available=[1,2,3]. k=2 (0-indexed). Factorials: 0!=1, 1!=1, 2!=2.

• i=3: 2 // 2! = 2//2 = 1. Pick available[1]=2. k=2%2=0. Available=[1,3].
• i=2: 0 // 1! = 0. Pick available[0]=1. k=0%1=0. Available=[3].
• i=1: Pick available[0]=3. Result: "213".

Common mistakes candidates make

• Not converting k to 0-indexed before processing.
• Off-by-one in factorial computation.
• Using a list for available (O(n) removal instead of O(1) with linked list or sorted list).
• Not handling n=1 edge case.

Interview preparation tip

The factoradic system is a base-(n, n-1, ..., 1) number system. Understanding it conceptually: for n numbers with (n-1)! permutations per leading digit, k//(n-1)! gives the leading digit index. Then recurse on the remaining n-1 digits with k%(n-1)!. Practice this on "decode permutation from integer" problems. Precomputing factorials avoids repeated computation.