# Permutation Sequence

This page explains Java solution to problem `Insert Interval` using `Permutations`.

## Problem Statement

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 for `n = 3`:

• `123`
• `132`
• `213`
• `231`
• `312`
• `321`

Given `n` and `k`, return the `kth` permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class PermutationSequence {
public String getPermutation(int n, int k) {
List<Integer> numbers = new ArrayList<>();
int[] factorial = new int[n];
factorial = 1;
for(int i = 1; i < n; i++) {
factorial[i] = factorial[i - 1] * i;
}

//We want kth element, so we skip (k - 1) elements as below
k--;
StringBuilder sb = new StringBuilder();
for(int i = n - 1; i >= 0; i--) {
int index = k / factorial[i];
k -= index * factorial[i];
sb.append(numbers.get(index));
numbers.remove(index);
}
return sb.toString();
}
}
``````

## Time Complexity

O(N)
Where N is number of elements for permutation.

O(N)