Leetcode: 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.

Note: Given n will be between 1 and 9 inclusive.

Understand the problem:
The problem asks for return the kth permutation sequence. This question could be very similar to the permutation problem, so we can use a counter to count for the kth sequence. 
The crux of the problem is the order, so if we simply swap the ith and start th of the element of the previous approach, it will not  output the sequence in order. For e.g. when n = 3, the output is 
123, 132, 213, 231, 321, 312. So when i - start > 1, we need to swap the following elements as well. 

Naive Solution:
So the naive solution is do the permutation "in-order" and note down the nth sequence. When it meets the kth sequence, return the kth sequence. 

public class Solution {
    int count = 0;
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }
        
        int num[] = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = i + 1;
        }
        
        getPermutationHelper(num, k, 0);
        
        return Arrays.toString(num);
    }
    
    private boolean getPermutationHelper(int[] num, int k, int start) {
        if (start >= num.length) {
            count++;
            if (count == k) {
                return true;
            }
            return false;
        }
        
        for (int i = start; i < num.length; i++) {
            for (int j = start; j < i; j++) {
                swap(num, j, i);
            }
            if (getPermutationHelper(num, k, start + 1) == true) {
                return true;
            }
            
            for (int j = i - 1; j >= start; j--) {
                swap(num, j, i);
            }
        }
        return false;
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}

Discussion:
The time complexity of this solution is factorial, so it got the TLE error on OJ. We must find another faster way to solve this question. 

A better solution:

public class Solution {
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }
        
        ArrayList<Integer> num = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            num.add(i);
        }
        
        // calculate the factorial
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            factorial *= i;
        }
        
        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            factorial /= (n - i);
            int index = k / factorial;
            sb.append(num.get(index));
            
            num.remove(index);
            
            // update current k
            k %= factorial;
        }
        
        return sb.toString();
    }
}