Permutation Sequence

Given n and k, return the k-th permutation sequence.

Have you met this question in a real interview? 

Yes

Example

For n = 3, all permutations are listed as follows:

"123"
"132"
"213"
"231"
"312"
"321"

If k = 4, the fourth permutation is "231"

Note

n will be between 1 and 9 inclusive.

Challenge

O(n*k) in time complexity is easy, can you do it in O(n^2) or less?

class Solution {

    /**

      * @param n: n

      * @param k: the kth permutation

      * @return: return the k-th permutation

      */

    public String getPermutation(int n, int k) {

        

        ArrayList<Integer> elements = new ArrayList<Integer>();

        int factor = 1;

        for(int i = 1; i < n; i++){

            factor *= i;

            elements.add(i);

        }

        elements.add(n);

        k--;

        StringBuffer buffer = new StringBuffer();

        for(int i = 1; i <= n; i++){

            int idx = k / factor;

            buffer.append(elements.get(idx));

            elements.remove(idx);

            if(i == n) break;

            k %= factor;

            factor /= (n-i);

        }

        return buffer.toString();

        

    }

}