Permutation Sequence: The Factorial Number System

Given n and k, return the kth permutation sequence of the numbers [1, 2, ..., n].

This is LeetCode 60: Permutation Sequence. The set [1, 2, 3] has six permutations in lexicographic order: "123", "132", "213", "231", "312", "321". If n = 3 and k = 3, the answer is "213". If n = 4 and k = 9, the answer is "2314".

You could generate all n! permutations and pick the kth one, but that blows up fast. For n = 9, there are 362,880 permutations. The factorial number system lets you compute the answer directly by dividing k by factorials to determine which number goes at each position, one digit at a time.

The approach

The key insight is that permutations in lexicographic order form a predictable structure. For n numbers, the first (n-1)! permutations all start with the smallest number, the next (n-1)! start with the second smallest, and so on. This pattern repeats recursively at every position.

To find the kth permutation without listing them all:

1. Start with the list of available numbers [1, 2, ..., n].
2. Subtract 1 from k to convert to 0-based indexing.
3. For each position from left to right, compute index = k // (n-1)!. This tells you which available number goes at this position. Then update k = k % (n-1)! and remove the chosen number from the list.
4. Repeat, using the next smaller factorial, until all positions are filled.

Each division by a factorial skips over entire blocks of permutations. You never generate any permutation you do not need.

The solution

def getPermutation(n: int, k: int) -> str:
    factorials = [1] * n
    for i in range(1, n):
        factorials[i] = factorials[i - 1] * i

    nums = list(range(1, n + 1))
    k -= 1
    result = []

    for i in range(n, 0, -1):
        f = factorials[i - 1]
        index = k // f
        result.append(str(nums[index]))
        nums.pop(index)
        k %= f

    return "".join(result)

The factorials array precomputes 0! through (n-1)!. The nums list tracks which numbers are still available. After converting k to 0-based, the loop processes one position per iteration.

At each step, k // f determines which block of permutations you fall into, which maps directly to an index in the remaining nums list. After picking that number, k %= f gives the position within that block, and the process continues with one fewer number and one smaller factorial.

The nums.pop(index) call removes the chosen number so it cannot be picked again. Since the list is always sorted, picking by index automatically respects lexicographic order.

Visual walkthrough

Let's trace through n = 4, k = 9 step by step. The available numbers start as [1, 2, 3, 4] and k becomes 8 after converting to 0-based.

Each step divides k by the current factorial to find which group the answer falls in, picks the number at that index, and takes the remainder as the new k for the next position. The result builds up as "2314".

Complexity

Time is O(n^2). The outer loop runs n times. Inside each iteration, nums.pop(index) takes O(n) in the worst case because removing from the middle of a list requires shifting elements. That gives O(n) iterations times O(n) per removal, so O(n^2) total.

Space is O(n). The factorials array, the nums list, and the result list each use O(n) space.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently.

Factorial number system

The factorial number system represents a number as a sum of multiples of factorials: k = d_{n-1} * (n-1)! + d_{n-2} * (n-2)! + ... + d_1 * 1! + d_0 * 0!, where each digit d_i satisfies 0 to i. This is the same idea behind converting between number bases, except the base changes at each position.

In this problem, the "digits" of the factorial representation tell you which element to pick from the remaining list at each position. The first digit (from k // (n-1)!) picks from n elements, the second digit (from the remainder divided by (n-2)!) picks from n-1 elements, and so on. This one-to-one mapping between factorial representations and permutations is why the approach works.

Index-based selection from a shrinking list

At each step, you pick the element at a computed index from a list, then remove it. This "select and remove" operation appears in problems involving sampling without replacement, ranking/unranking permutations, and reservoir sampling. The key property is that removing an element preserves the relative order of the remaining elements, so subsequent index lookups still point to the correct element.

nums = [1, 2, 3, 4]
index = 1
picked = nums[index]    # 2
nums.pop(index)          # nums is now [1, 3, 4]

This micro-pattern is simple, but getting the index arithmetic right under pressure matters. The factorial number system tells you which index to pick. The shrinking list ensures each number is used exactly once.

Edge cases

k = 1 (first permutation). After converting to 0-based, k = 0. Every division 0 // f gives 0, so you always pick the smallest remaining number. The result is "123...n", which is the sorted order. Correct.

k = n! (last permutation). After converting, k = n! - 1. At each step, you pick the largest available index. The result is "n(n-1)...21", the reverse-sorted order. Correct.

n = 1. Only one permutation exists: "1". The loop runs once, picks the only element, and returns "1".

From understanding to recall

You understand the factorial number system. You can trace through an example and see how each division picks the right element. But can you write the solution from scratch in under two minutes?

That is what interviews demand. Under pressure, small details trip people up: forgetting to subtract 1 from k, using the wrong factorial at each step, or indexing into the list incorrectly after a removal. These are not conceptual gaps. They are recall problems.

The factorial number system and index-based selection are each small enough to drill independently. When you can write both from memory, the full solution is just combining them in a loop. Spaced repetition turns understanding into instant recall, so when you see "kth permutation" in an interview, the code flows out without hesitation.

Related posts

• Permutations - Generates all n! permutations using backtracking. Understanding the full permutation space helps you see why the factorial number system can index directly into it.
• Next Permutation - Finds the lexicographically next permutation in O(n) time. A different approach to navigating permutation order, using suffix analysis instead of factorial decomposition.

CodeBricks breaks Permutation Sequence into its factorial number system and index-based selection building blocks, then drills them independently with spaced repetition. You type each brick from scratch until it is automatic. When the problem shows up in your interview, you do not think about it. You just write it.