Permutation Sequence — Hard Problem & Solution

Problem statement

The numbers 1, 2, ..., n have n! orderings. Write each ordering as a string of digits and sort them; for n = 3 the list is "123", "132", "213", "231", "312", "321".

Return the k-th string in that sorted list (counting from 1).

Example 1

Input: n = 3, k = 3
Output: 213

Example 2

Input: n = 4, k = 9
Output: 2314

Example 3

Input: n = 3, k = 1
Output: 123

Constraints

• 1 <= n <= 9
• 1 <= k <= n!

How to solve Permutation Sequence

The sorted permutations come in blocks: all those starting with the smallest available digit, then the next, and so on, each block of size (remaining - 1)!. Dividing the zero-based index by that block size picks the next digit.

Approach

1. Precompute factorials up to n! and keep the available digits 1..n in increasing order.
2. Let r = k - 1. For i from n down to 1: idx = r / (i - 1)!, r = r % (i - 1)!.
3. Append the idx-th available digit and remove it from the list.
4. Return the built string.

Why it works

Among the permutations of the remaining digits, the ones beginning with the j-th smallest digit occupy exactly positions j · (i-1)! to (j+1) · (i-1)! - 1 in sorted order. So the quotient selects the right block and the remainder is the index inside it, recursively.

Complexity

• Time — O(n^2) (removing from the digit list)
• Space — O(n)

Pitfalls

• Convert k to a zero-based index first; using k directly is off by one block at every boundary.
• Remove each chosen digit from the available list so it is not reused.
• The answer is a string of digits, not a number.

Reference solution

Python

def getPermutation(n: int, k: int) -> str:
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
    digits = [str(i) for i in range(1, n + 1)]
    r = k - 1
    out = []
    for i in range(n, 0, -1):
        idx = r // fact[i - 1]
        r %= fact[i - 1]
        out.append(digits.pop(idx))
    return ''.join(out)

JavaScript

var getPermutation = function(n, k) {
    var fact = [1];
    for (var i = 1; i <= n; i++) fact.push(fact[i - 1] * i);
    var digits = [];
    for (var d = 1; d <= n; d++) digits.push(d);
    var r = k - 1;
    var out = '';
    for (var j = n; j >= 1; j--) {
        var idx = Math.floor(r / fact[j - 1]);
        r %= fact[j - 1];
        out += digits[idx];
        digits.splice(idx, 1);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Number of Squareful Arrays Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard
• Expression Add Operators Hard
• Transform to Chessboard Hard
• Stone Game V Hard