How do you approach Permutation Sequence?

There are (n-1)! permutations for each choice of the first digit.

What are common mistakes on Permutation Sequence?

Overflowing at an intermediate step even though the final answer fits. Assuming a modulo is non-negative. In most languages -1 % n is negative, which breaks cyclic indexing. Testing floating-point values for exact equality where integer arithmetic would have been exact.

← Back to problems

Permutation Sequence

HardAlgorithms

Description

The set `[1, 2, ..., n]` has `n!` permutations. Listing them in order gives a sequence; given `n` and `k`, return the `k`-th permutation sequence (1-indexed) as a string.

Example 1

Input: n = 3, k = 3

Output: "213"

Explanation: Order: 123, 132, 213, ... the 3rd is 213.

Example 2

Input: n = 4, k = 9

Output: "2314"

Explanation: The 9th permutation of 1..4.

Constraints

- 1 <= n <= 9 - 1 <= k <= n!

Permutation Sequence: approach, complexity and pitfalls

A hard math problem, graded against 4 test cases (2 of them hidden).

The pattern: Math

Number theory, digit manipulation, and closed-form reasoning.

Reach for it when you see: Primes, digits, base conversion, or a problem with a formula hiding behind it.

More Mathproblems →

If you are stuck

Show the 2-step hint ladder

There are (n-1)! permutations for each choice of the first digit.
Use factorials to pick each digit directly instead of enumerating permutations.

The optimal approach

Show the approach: The approach

Factorial number system. Precompute factorials. With `k` made 0-indexed, the first digit's position is `k / (n-1)!`; remove it, take `k % (n-1)!`, and repeat for the rest. This builds the answer in O(n²) without listing permutations.

Time: O(n²). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Math mistakes

These apply to the pattern as a whole, not just this problem.

Overflowing at an intermediate step even though the final answer fits.
Assuming a modulo is non-negative. In most languages `-1 % n` is negative, which breaks cyclic indexing.
Testing floating-point values for exact equality where integer arithmetic would have been exact.