Last updated on October 9th, 2024 at 10:44 pm

Here, We see Permutation Sequence LeetCode Solution. This Leetcode problem done in many programming language like C++, Java, JavaScript, Python etc. with different approach.

List of all LeetCode Solution

Permutation Sequence LeetCode Solution

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:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "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"

Example 3:

Input: n = 3, k = 1
Output: "123"

1. Permutation Sequence Leetcode Solution C++

class Solution {
public:
    string getPermutation(int n, int k) {
    int pTable[10] = {1};
    for(int i = 1; i <= 9; i++){
        pTable[i] = i * pTable[i - 1];
    }
    string result;
    vector<char> numSet;
    numSet.push_back('1');
    numSet.push_back('2');
    numSet.push_back('3');
    numSet.push_back('4');
    numSet.push_back('5');
    numSet.push_back('6');
    numSet.push_back('7');
    numSet.push_back('8');
    numSet.push_back('9');
    while(n > 0){
        int temp = (k - 1) / pTable[n - 1];
        result += numSet[temp];
        numSet.erase(numSet.begin() + temp);
        k = k - temp * pTable[n - 1];
        n--;
    }
    return result;        
    }
};

2. Permutation Sequence Leetcode Solution Java

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> num = new LinkedList<Integer>();
        for (int i = 1; i <= n; i++) num.add(i);
        int[] fact = new int[n];  // factorial
        fact[0] = 1;
        for (int i = 1; i < n; i++) fact[i] = i*fact[i-1];
        k = k-1;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i > 0; i--){
            int ind = k/fact[i-1];
            k = k%fact[i-1];
            sb.append(num.get(ind));
            num.remove(ind);
        }
        return sb.toString();        
    }
}

3. Permutation Sequence Leetcode Solution JavaScript

var getPermutation = function(n, k) {
    let factorial = [1];
    for (let i=1;i<=n;i++) factorial[i]= i * factorial[i-1];
    let nums = Array.from({length: n}, (v, i) => i+1);
    let res = "";
    for (let i=n;i>0;i--) {
        index = Math.ceil(k / factorial[i - 1]); // decide to use which permutation set
        res+=nums[index - 1];
        nums.splice(index - 1, 1);
        k -= (factorial[i-1] * (index - 1));
    }
    return res;    
};

4. Permutation Sequence Leetcode Solution Python

class Solution(object):
    def getPermutation(self, n, k):
        numbers = range(1, n+1)
        permutation = ''
        k -= 1
        while n > 0:
            n -= 1
            # get the index of current digit
            index, k = divmod(k, math.factorial(n))
            permutation += str(numbers[index])
            # remove handled number
            numbers.remove(numbers[index])

        return permutation