# O(n) java solution with comments, 250ms

• ``````public String getPermutation(int n, int k) {
if(n==1){
return "1";
}
int frac=1;

// a[i] records how many (n-1-i)!permutuations we need
// eg. if n=8, a[0],a[1],a[2] means how many 7! 6! and 5! permutaions we need
// the idea is that a[0]+a[1]+...+a[n-1]=k
int[] a=new int[n];
for(int i=1;i<n;i++){
frac*=i;
}
int finish=0;
for(int i=0;i<n-1;i++){
a[i]=(k-k%frac)/frac;
k-=a[i]*frac;

// if we already add permutations up to k, we can stop processing the remaining permutations
if(k==0){
finish=i;
break;
}

frac/=n-1-i;
}
TreeSet<Integer> ts=new TreeSet<>();
for(int i=1;i<=n;i++){
}
StringBuffer sb=new StringBuffer();

for(int i=0;i<finish;i++){
int mth;
mth=mthEle(a[i]+1,ts);
a[i]=mth;
ts.remove(mth);
sb.append(a[i]);
}

// note that on the final bit, we need to substarct by 1, because the following (n-finish-1)! will account for 1
int fin=mthEle(a[finish],ts);
a[finish]=fin;
ts.remove(fin);
sb.append(a[finish]);

// get the largest permutation of the remaining, i.e, permute them in the descending order
Iterator<Integer> it=ts.descendingIterator();
while(it.hasNext()){
sb.append(it.next());
}
return sb.toString();

}
public int mthEle(int m,TreeSet<Integer> ts){
//return the mth element which is larger than the smallest element in ts
Iterator<Integer> it = ts.iterator();
if(m==0){
return ts.first();
}
int i = 0;
Integer current = null;
while(it.hasNext() && i < m) {
current = it.next();
i++;
}
return current;
}``````

• Does the remove operation of TreeSet take O(log n) time? Because it is backed by a balanced tree. Therefore it is actually O(nlog n) ?

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