Kth permutation sequence of 1..N
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"
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;}