Thinking process

https://discuss.leetcode.com/topic/17348/explain-like-i-m-five-java-solution-in-o-n/12

Time Complexity

O (n ^ 2)

remove an element from a list takes O(n) time

public class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder result = new StringBuilder();
        List<Integer> nums = new ArrayList<>();
        int factorial = 1;
        for (int i = 1; i <= n; ++i) {
            factorial *= i;
            nums.add(i);
        }
        for (int i = 0, l = k - 1; i < n; ++i) {
            factorial /= (n - i);
            int index = l / factorial;
            result.append(nums.remove(index));
            l -= index * factorial;
        }

        return result.toString();
    }
}