Introduction

The naive way to find the kth permutation is to generate every permutation, sort them, and pick one. That works for tiny inputs, but it becomes impractical very quickly because the number of permutations grows as n!.

The Key Idea: Factorial Blocks

List the numbers from 1 to n in lexicographic order. For a fixed first digit, the remaining n - 1 digits can be arranged in (n - 1)! ways. That means permutations are naturally grouped into blocks of equal size.

For n = 4, each leading digit owns 3! = 6 permutations:

• '1xxx covers permutations 1 through 6'
• '2xxx covers permutations 7 through 12'
• '3xxx covers permutations 13 through 18'
• '4xxx covers permutations 19 through 24'

So if k = 9, the answer is in the block starting with 2 because 9 falls in the second group of six.

Converting k Into Choices

The standard trick is to convert k from one-based indexing to zero-based indexing first. That makes division cleaner.

Suppose n = 4 and k = 9.

1. Start with available digits: [1, 2, 3, 4]
2. Convert k to zero-based: k = 8
3. Compute 3! = 6
4. Choose index 8 // 6 = 1, so the first digit is 2
5. Remove 2, leaving [1, 3, 4]
6. Update k = 8 % 6 = 2
7. Compute 2! = 2
8. Choose index 2 // 2 = 1, so the next digit is 3
9. Remove 3, leaving [1, 4]
10. Update k = 2 % 2 = 0
11. Compute 1! = 1
12. Choose index 0 // 1 = 0, so the next digit is 1
13. The remaining digit is 4

The result is 2314.

Python Implementation

Here is a complete implementation that runs in O(n^2) time because removing from the middle of a list costs linear time. For interview-sized inputs, that is usually fine.

1from math import factorial
2
3
4def kth_permutation(n: int, k: int) -> str:
5    digits = [str(i) for i in range(1, n + 1)]
6    k -= 1
7    answer = []
8
9    for remaining in range(n, 0, -1):
10        block_size = factorial(remaining - 1)
11        index = k // block_size
12        answer.append(digits.pop(index))
13        k %= block_size
14
15    return "".join(answer)
16
17
18print(kth_permutation(4, 9))

Output:

2314

Why This Works

At every step, permutations are partitioned into equal blocks. The block size depends only on how many positions remain. Integer division tells you which block contains the desired answer, and modulo tells you where to continue searching inside that block.

This is sometimes called the factorial number system because the position is described using factorial-sized units rather than powers of ten.

Handling Invalid Input

The valid range for k is from 1 to n!. If k falls outside that range, there is no such permutation.

1from math import factorial
2
3
4def safe_kth_permutation(n: int, k: int) -> str:
5    total = factorial(n)
6    if k < 1 or k > total:
7        raise ValueError(f"k must be between 1 and {total}")
8    return kth_permutation(n, k)

This check prevents silent failures or index errors.

Complexity Discussion

Generating all permutations takes O(n! * n) time and a large amount of memory if you store them. The factorial-block method avoids that explosion. You only build the answer one digit at a time.

The implementation above uses a list for the remaining digits, so each pop(index) may shift elements. That gives O(n^2) time overall. More advanced data structures can reduce selection cost, but for the common interview version of the problem, the list-based solution is both correct and easy to explain.

Common Pitfalls

The most common bug is forgetting that the problem statement usually counts permutations starting at 1, while Python lists are zero-based. If you do not subtract 1 from k at the start, every block calculation is off.

Another mistake is using n! at every step instead of (remaining - 1)!. The block size should depend on the number of digits left after fixing the current position.

A third problem is not validating k. If k is larger than n!, eventually the selected index will be out of range.

Summary

• The kth permutation can be found without generating every permutation.
• Permutations are grouped into factorial-sized blocks.
• Convert k to zero-based indexing before doing the math.
• At each step, use division to choose a digit and modulo to update the remainder.
• A simple list-based implementation is usually the right balance of clarity and performance.