10. Permutation Sequence

Difficulty:HardPattern:Factorial Math Block ParsingTime:O(n^2)Space:O(n)

The set [1, 2, 3, ..., n] contains n! unique permutations. Given n and k, return the $k$-th permutation sequence.

How It Works & Algorithmic Design

Solves using Factorial Block Deconstruction:

Factorial Lookup: Precompute factorials: fact[i] = i!.
Numbers List: Build array numbers = [1, 2, ..., n].
Zero-Indexing: Set k = k - 1.
Group Selection Loop (from $i = n$ down to $1$):
- Block size $S = (i - 1)!$.
- Index $idx = \lfloor k / S \rfloor$.
- Append numbers[idx] to result string and remove from numbers.
- Update k = k % S.

Why This Approach Works Best

Calculates the $k$-th permutation directly in $O(n^2)$ time, avoiding $O(n!)$ generation.

Example Walkthrough

Input: n = 3, k = 3

Target permutation.

Permutation List: 1: "123", 2: "132", 3: "213", 4: "231"...

Ordered permutations.

Output: "213"

3rd permutation sequence.

Answer: Permutation Sequence implementation

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

💡 Directly locate target permutation digits using factorial block division.

Key Takeaways

Converts $k$ to 0-based indexing first.
Determines digits directly using block division by $(i-1)!$.
Runs in $O(n^2)$ time due to list element removal.