0060-permutation-sequence.java

classSolution {

// Time complexity O(N^2) becuase of remove method
publicStringgetPermutation(intn, intk) {
StringBuilderkthPerm = newStringBuilder();
intfact = 1;
//this list will contain all the values from 1 to n for reference
ArrayList<Integer> list = newArrayList<>();
for (inti = 1; i < n; i++) {
fact = fact * i;
list.add(i);
 }
list.add(n);
k--;
while (true) {
kthPerm.append(list.get(k / fact));
list.remove(k / fact);
if (list.size() == 0) break;
k = k % fact;
fact = fact / (list.size());
 }
returnkthPerm.toString();
 }

 {
//Bruteforce solution (gives TLE) similar to Next Permutation problem no.31

// public String getPermutation(int n, int k) {
// int[] num = new int[n];
// for (int i = 1; i<=n; i++) {
// num[i-1] = i;
// }
// for (int i = 1; i<k; i++) {
// nextPermutation(num);
// }
// return numToString(num);
// }

// public void nextPermutation(int[] nums) {
// int pivot = nums.length-1;
// while (pivot>0 && nums[pivot]<nums[pivot-1]) {
// pivot--;
// }
// pivot--;
// int j = nums.length-1;
// while (j>0 && nums[j]<nums[pivot]) {
// j--;
// }
// System.out.println(pivot+" "+j);
// swap(nums, j, pivot);
// reverse(nums, pivot+1);
// }

// public void reverse(int[] num, int start) {
// int end = num.length-1;
// while (start<end) {
// int temp = num[start];
// num[start] = num[end];
// num[end] = temp;
// start++;
// end--;
// }
// }

// public void swap(int[] num, int i, int j) {
// int temp = num[i];
// num[i] = num[j];
// num[j] = temp;
// }

// public String numToString(int[] arr) {
// StringBuilder sb = new StringBuilder();
// for (int num: arr)
// sb.append(num);
// return sb.toString();
// }

 }
}