Kth permutation sequence of 1..N

Medium

Problem

The n! permutations of [1..n] are listed in lexicographic order. Return the kth one (1-indexed) without generating the others.

Example 1

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

123, 132, 213, …

Example 2

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

Also asked as: Find the K-th Permutation Sequence of first N natural numbers

Test cases

Case 1

Input:    3, 3
Expected: "213"

Case 2

Input:    4, 9
Expected: "2314"

Case 3

Input:    3, 6
Expected: "321"

Case 4

Input:    1, 1
Expected: "1"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Factorial number system (no enumeration)

Time O(n²)Space O(n)

The first digit is determined by k / (n−1)!; remove it, take k mod (n−1)!, repeat. O(n²) without generating permutations.

function getPermutation(n, k) {
const fact = [1];
for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
const digits = Array.from({ length: n }, (_, i) => i + 1);
k--; // 0-indexed
let res = '';
for (let i = n; i >= 1; i--) {
const idx = Math.floor(k / fact[i - 1]);
res += digits[idx];
digits.splice(idx, 1);
k %= fact[i - 1];
}
return res;
}