Kth Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3 ) :

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

For example, given n = 3, k = 4, ans = "231"

Method:

2 1 0
0 0 0  -> 123 -> 0
0 1 0  -> 132 -> 1
1 0 0  -> 213 -> 2
1 1 0  -> 231 -> 3
2 0 0  -> 312 -> 4
2 1 0  -> 321 -> 5

For each digit, if we can know it's sequence then we can pick the number.
For example, if n = 3, k = 4, we want to find 1 1 0.
we subtract k by 1 to get 3, then the first digit we get 1 because 3 / 2! = 1, so we know we want the second biggest number for the first dight, then we have target = 3 - 1 * 2! = 1, so the second digit we want 1 / 1! = 1, we still want the second biggest number for the second digit. so we get 1 1 0 for the indices. Then we can pick the numbers to generate the string, for first digit, we get 2 since it's the second largest, for second digit we choose 3 because 3 is the second largest (since 2 is used), third digit we have no choice but 1.

Solution:

Time: O(n)
Space: O(n)

import java.math.*;

public class Solution {
    public String getPermutation(int A, int B) {
        List<Integer> indices = new ArrayList<>();
        BigInteger[] fact = factorial(A);
        B = B - 1;
        BigInteger target = new BigInteger(B + "");
        for (int i = A - 1; i >= 0; i --) {
            if (i == 0) {
                indices.add(0);
            } else {
                BigInteger index = target.divide(fact[i]);
                indices.add(index.intValue());
                target = target.subtract(index.multiply(fact[i]));
            }
        }
        StringBuilder sb = new StringBuilder();
        List<String> numbers = new LinkedList<>();
        for (int i = 1; i <= A; i ++) {
            numbers.add(i + "");
        }
        for (int index : indices) {
            // System.out.println(index);
            sb.append(numbers.get(index));
            numbers.remove(index);
        }
        return sb.toString();
    }
    
    private BigInteger[] factorial(int n) {
        BigInteger[] fact = new BigInteger[n + 1];
        fact[0] = BigInteger.ONE;
        for (int i = 1; i <= n; i ++) {
            fact[i] = fact[i - 1].multiply(new BigInteger(i + ""));
        }
        return fact;
    }
}