Permutation Sequence

hard math recursion

Problem

Given n and k, return the k-th permutation sequence of the numbers 1..n (1-indexed). Don't generate all n! permutations — derive the answer arithmetically.

Inputn = 3, k = 3

Output"213"

Sorted perms: 123, 132, 213, 231, 312, 321. The 3rd is "213".

def get_permutation(n, k):
    fact = [1] * (n + 1)
    for i in range(1, n + 1): fact[i] = fact[i - 1] * i
    nums = list(range(1, n + 1))
    k -= 1
    out = []
    for i in range(n, 0, -1):
        idx, k = divmod(k, fact[i - 1])
        out.append(str(nums.pop(idx)))
    return "".join(out)

function getPermutation(n, k) {
  const fact = [1];
  for (let i = 1; i <= n; i++) fact.push(fact[i - 1] * i);
  const nums = [];
  for (let i = 1; i <= n; i++) nums.push(i);
  k -= 1;
  let out = "";
  for (let i = n; i >= 1; i--) {
    const idx = Math.floor(k / fact[i - 1]);
    k -= idx * fact[i - 1];
    out += nums.splice(idx, 1)[0];
  }
  return out;
}

class Solution {
    public String getPermutation(int n, int k) {
        int[] fact = new int[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) nums.add(i);
        k -= 1;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i >= 1; i--) {
            int idx = k / fact[i - 1];
            k %= fact[i - 1];
            sb.append(nums.remove(idx));
        }
        return sb.toString();
    }
}

string getPermutation(int n, int k) {
    vector<int> fact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
    vector<int> nums;
    for (int i = 1; i <= n; i++) nums.push_back(i);
    k -= 1;
    string out;
    for (int i = n; i >= 1; i--) {
        int idx = k / fact[i - 1];
        k %= fact[i - 1];
        out += (char)('0' + nums[idx]);
        nums.erase(nums.begin() + idx);
    }
    return out;
}

Explanation

Generating all n! permutations to grab the k-th one would be wasteful. Instead we build the answer digit by digit using factorials to figure out each leading number directly.

Here is the key idea: if you fix the first digit, the remaining n-1 numbers can be arranged in (n-1)! ways. So the permutations come in blocks of size (n-1)!. Dividing the (0-based) k by that block size tells you which remaining number to place first; the remainder becomes the new k for the smaller problem.

We precompute the factorials and keep a pool nums of unused numbers. We convert to 0-based with k -= 1, then repeat: idx = k // (i-1)! picks the index in the pool, we remove that number into the result, and set k = k % (i-1)!. Each pick shrinks the pool by one.

Example: n = 3, k = 3. Make k = 2 (0-based). Blocks are size 2! = 2, so idx = 2 // 2 = 1 picks nums[1] = 2; remainder 0. Next block size 1! = 1, idx = 0 picks 1, then the last is 3. Result: "213".

We do n picks and each removal from the list is linear, so the running time is quadratic in n with linear space.

Time: O(n²) (linear removal from list) Space: O(n)