Permutation Sequence

Do not generate the permutations. Locate the block, choose its digit, and repeat.

Read the contract and spot the structure

The task is precise:

• The available values are 1 through n.
• Their n! permutations are ordered lexicographically.
• k is one-based: k = 1 means the first permutation.
• Return the k-th permutation as a string.
• The constraints are 1 <= n <= 9 and 1 <= k <= n!.

For n = 3, the ordered permutations are:

123
132
213
231
312
321

The obvious approach is to generate this sequence and take position k - 1. That approach matches the definition, but it ignores the structure that makes direct selection possible.

The key state is small:

1. unused: the sorted values not yet placed.
2. rank: the target's zero-based position among permutations of exactly those unused values.
3. result: the prefix selected so far.

Every time we fix one value, the remaining permutations split into equal-sized lexicographic blocks. The problem becomes a sequence of state transitions:

Find the block containing the residual rank, select that block's first value, remove it, and continue with the suffix.

This is a rank-selection problem, not a permutation-generation problem.

That distinction also separates this task from Next Permutation. Next Permutation transforms one existing arrangement into its immediate successor. Permutation Sequence selects an arrangement by ordinal rank.

Reject enumeration, keep it as a test oracle

A brute-force solution would:

1. Generate all permutations of [1, 2, ..., n].
2. Keep them in lexicographic order.
3. Return the element at index k - 1.

This is useful as a baseline because it makes the contract visible. It is also the wrong submitted algorithm. The requested output contains one permutation, while enumeration constructs all n! candidates and carries nearly all of that work to the end.

For example, when n = 9, the search space contains 9! permutations. The direct method never needs to materialize those candidates.

Brute force still has a valuable role: use it as a comparison oracle for tiny values of n. Generate every permutation for n <= 6, compare its indexed result with the factorial-selection method, and let mismatches expose arithmetic or removal errors. A slow implementation is often an excellent debugger even when it is a poor production algorithm.

The optimization target is therefore not “generate permutations faster.” It is:

Count how many permutations share each possible prefix, then skip whole groups.

Derive the factorial blocks

Suppose r values remain and we are choosing the next value.

If we fix one candidate, there are r - 1 values left. Those values can be arranged in:

[ (r - 1)! ]

ways.

So every possible next value owns a block of exactly (r - 1)! permutations.

Because candidates are considered in ascending order, those blocks appear consecutively in lexicographic order.

For n = 3, the first position has block size 2! = 2:

1 -> 123, 132
2 -> 213, 231
3 -> 312, 321

Once the first value is selected, the next position has block size 1! = 1. The same rule applies recursively to the suffix.

The input k is one-based, but quotient and remainder arithmetic is naturally zero-based. Convert once:

rank = k - 1

At a step with r unused values:

block_size   = (r - 1)!
candidate_ix = rank // block_size
rank         = rank % block_size

candidate_ix tells us which unused value to select. The new rank tells us where the target lies inside that selected block.

This is the factorial number system in operational form. The successive quotients are the digits of the target rank relative to factorial block sizes.

A compact state trace

For n = 4, k = 9, the initial zero-based rank is 8.

Unused values	Block size	Rank	Quotient	Selected	New rank
[1, 2, 3, 4]	3! = 6	8	1	2	2
[1, 3, 4]	2! = 2	2	1	3	0
[1, 4]	1! = 1	0	0	1	0
[4]	0! = 1	0	0	4	0

The result is:

2314

The first quotient skips the six permutations beginning with 1. The second quotient skips the two permutations beginning with 21 within the remaining search space. After that, the residual rank is zero, so we repeatedly take the smallest remaining value.

Define the state transition and invariant

Precompute factorials from 0! through (n - 1)!. We never need n! to select a digit, although it is useful when validating k outside the stated contract.

Initialize:

factorial[i] = i!
unused = [1, 2, ..., n]
rank = k - 1
result = []

At every iteration:

1. Let r = len(unused).
2. Set block_size = factorial[r - 1].
3. Compute candidate_index = rank // block_size.
4. Remove unused[candidate_index] and append it to the result.
5. Set rank = rank % block_size.

The invariant is the important part:

Before each iteration, rank identifies the target among all permutations of the current unused values, ordered lexicographically.

Initially, this is true because rank = k - 1 identifies the requested permutation in the full ordered set. Each transition preserves it:

• The quotient selects the block containing the target.
• Removing the selected value restricts the problem to that block.
• The remainder gives the target's position inside the block.

A sorted Python list is the right data structure for these constraints. There are at most nine values, so list indexing and removal keep the implementation visible and auditable. An order-statistics structure would support faster selection and deletion for much larger n, but it would add machinery that the contract does not require.

Why the selection is correct

The proof has three small pieces.

Prefix-block lemma

With r values remaining, fixing the next value leaves r - 1 values to arrange. Therefore, that fixed value prefixes exactly:

[ (r - 1)! ]

permutations.

Since the candidates are considered in ascending order, each candidate owns one contiguous lexicographic block of that size.

Selection lemma

Let rank be zero-based and let block_size = (r - 1)!.

The block index is:

[ \left\lfloor \frac{rank}{block_size} \right\rfloor ]

That is exactly rank // block_size. The remainder:

[ rank \bmod block_size ]

is the target's zero-based position within the chosen block.

Because the valid rank is below the total number of remaining permutations, the quotient always identifies one of the available blocks.

Invariant preservation and termination

After selecting the block's first value, all permutations in other blocks are irrelevant. The remaining target is the suffix at the computed remainder rank among the remaining values. That is precisely the invariant for the next iteration.

Each iteration removes one value. After n selections, no suffix remains, and the output is the unique permutation at the requested rank.

The contract guarantees valid input. In reusable code, however, validate that:

1 <= k <= n!

Otherwise rank may point outside the available blocks, and the quotient could exceed the length of unused.

Dry-run the rank selection

The case n = 4, k = 9 shows the middle of the range:

rank = k - 1 = 8
unused = [1, 2, 3, 4]

First position

There are 3! = 6 completions for every first value.

candidate_index = 8 // 6 = 1

Index 1 in [1, 2, 3, 4] is 2. The target is in the block beginning with 2.

rank = 8 % 6 = 2
unused = [1, 3, 4]
result = "2"

Second position

There are 2! = 2 completions for every candidate.

candidate_index = 2 // 2 = 1

Index 1 in [1, 3, 4] is 3.

rank = 2 % 2 = 0
unused = [1, 4]
result = "23"

Third position

Now each candidate owns 1! = 1 completion.

candidate_index = 0 // 1 = 0

Select 1, then the final value must be 4:

result = "2314"

The boundary cases expose the indexing rule especially well.

For k = 1:

rank = 0

Every quotient is zero, so the algorithm selects the smallest remaining value each time:

1234

For k = n!, the initial rank is n! - 1. At every step, the quotient selects the largest remaining value:

4321

The common off-by-one bug is to divide the original one-based k directly. For n = 3, k = 2, the correct zero-based rank is 1, which selects 1 at the first position and then 3, producing 132. Using k = 2 directly gives a first quotient of 1, incorrectly jumping to the block beginning with 2.

Convert once. Then keep the entire algorithm zero-based.

Implement the Python solution

The code should mirror the derivation rather than hide it behind a clever formula.

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # factorial[i] stores i!
        factorial = [1] * (n + 1)
        for i in range(1, n + 1):
            factorial[i] = factorial[i - 1] * i

        unused = list(range(1, n + 1))
        result = []

        # Convert the one-based input rank to zero-based.
        rank = k - 1

        while unused:
            remaining = len(unused)
            block_size = factorial[remaining - 1]

            # The quotient identifies the lexicographic block.
            candidate_index = rank // block_size
            selected = unused.pop(candidate_index)
            result.append(str(selected))

            # The remainder identifies the rank inside that block.
            rank %= block_size

        return "".join(result)

Each variable has a direct obligation:

• factorial answers how many completions follow a fixed prefix.
• unused preserves the candidates in ascending order.
• rank tracks the target position in the current reduced search space.
• candidate_index chooses the correct block.
• rank %= block_size preserves the suffix rank after the block is selected.
• result stores the prefix that has already been fixed.

The final loop also handles the last value correctly. When one value remains:

block_size = factorial[0] = 1

The quotient is zero, the last value is removed, and the loop terminates.

An interview checklist:

1. Decrement k exactly once.
2. Use the current number of unused values.
3. Compute (remaining - 1)!, not remaining!.
4. Select and remove the value at the quotient index.
5. Update the rank with the remainder.
6. Convert selected integers to strings before joining.

Complexity, boundaries, and failure modes

Factorial preparation takes O(n) time and space.

The selection loop runs n times. Indexing a Python list is constant time, but pop(index) may shift later elements left. With at most n elements at each step, the total list-removal cost is:

[ O(n^2) ]

Appending to the result and constructing the final string add only O(n) work.

The auxiliary space is O(n):

• the factorial table stores n + 1 values,
• unused stores up to n values,
• result stores n characters.

That is fundamentally different from enumeration, which may require O(n!) candidate storage if all permutations are materialized.

Test these cases deliberately:

Case	What it checks
n = 1, k = 1	The smallest valid state and the 0! step
k = 1	Repeated smallest selections
k = n!	Repeated largest selections
n = 3, k = 3	A middle block transition, producing "213"
n = 4, k = 9	Quotients greater than zero followed by a zero residual rank
Final iteration	Correct use of 0! = 1
Invalid k in reusable code	Explicit range validation

The stated bound n <= 9 also keeps the factorial values within a small integer range. If you adapt the method to a different contract, choose a numeric type that safely represents the largest possible factorial and rank.

For much larger n, the mathematical method still works. The bottleneck changes from the arithmetic to candidate selection and removal. A linear list would make each choice increasingly expensive; an order-statistics structure can select and delete the q-th unused value more efficiently. That is a different engineering boundary, not a different algorithmic idea.

The transferable recognition rule is simple:

When ordered combinatorial objects split into equal-sized groups after fixing a prefix, track the residual rank instead of generating the candidates.

For this problem, debug the four moving parts in order: block size, quotient, remainder, and the one-based-to-zero-based conversion. Get those aligned, and the permutation stops being a vast search space. It becomes a short walk through factorial-sized blocks.