57. Permutation Sequence

Fixing the first digit partitions the permutations into blocks of (n-1)! each. Integer-divide (k-1) by (n-1)! to pick which unused number leads, then recurse on the remainder.

Pick digits by block

With n numbers, the permutations split into n blocks of (n-1)! each, grouped by their first element. So the leading element is nums[(k-1) // (n-1)!]; remove it and recurse with k = (k-1) % (n-1)! and one fewer number.

k -= 1
for i in range(n, 0, -1):
    f = (i-1)!
    idx = k // f
    append nums.pop(idx)
    k %= f

Worked example

n=4, k=9: with 3!=6 per block, (9-1)//6 = 1 → lead is 2; remainder 2 selects the rest → "2314".

Complexity

• Time: O(n²) (removing from a list).
• Space: O(n).

import java.util.ArrayList;
import java.util.List;

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