# Concise Java Solution withDetail Explanations

• The core idea is that denote (k-1) / (n-1)! by nth, nth represents the nth element in the candidate array should be appended to the answer string. Let's be more clear and take n = 4, k = 9 as example.

First build you candidate array list = {1,2,3,4}; Then nth = (k-1) / (n-1)! = 8/6 = 1. which mean arrayList[1] should be removed and place to your answer string. Now answer is "2".

Then assign k = (k-1) % (n-1)! +1 = 8%6 +1 = 3, and n= n -1 to decide the next digit. Similarly nth = (k-1) / (n-1)! = 3/2 = 1; note that now arrayList[1] = 3 since 2 has been removed in the previous iteration. Now answer is "23". Repeat that procedure until n ==0.

``````public String getPermutation(int n, int k) {

int[] factorial = new int[n];
ArrayList<Integer> candidate = new ArrayList<Integer>();

// Build factorial array
for (int i = 0; i < n; i++) {
factorial[i] = i == 0 ? 1 : i * factorial[i - 1];
}

StringBuilder sb = new StringBuilder();

while (n > 0) {
int remain = ((k - 1) % factorial[n - 1]) + 1;
sb.append(candidate.remove(((k - 1) / factorial[n - 1])));
n--;
k = remain;
}

return sb.toString();

}``````

• Thank you for your sharing. But I think remove() method takes O(n) time in your case, therefore it is actually O(n^2).

• Great observation ~ Thank you very much~ I am seeking a linear time solution~

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.