60. Permutation Sequence

Permutation Sequence

Problem Description

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"

 

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

Approach) Native

let getPermutation = function(n, k) {
    let permutationsNum = [1,2,6,24,120,720,5040,40320, 362880]
    let nums = []
    
    for(let i =0; i<n; i++) {
        nums.push(i+1)
    }
    
    let result = ''
    
    k = k -1
    n = n -1
    while(n >= 0) {
        let index = k/permutationsNum[n-1] | 0
        result = result + nums[index]
        nums.splice( index, 1 );
        k = k%permutationsNum[n-1]
        n = n - 1
    }
    return result 
};

Approach) Backtracking

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function(n, k) {
    
    function findPermutation(arr,curr){
        if(curr.length == n){
            counter++
            if(counter == k){
                res = curr.join('')
                return
            }
        }
        
        for(let i=0;i<arr.length;i++){
            curr.push(arr[i])
            findPermutation(arr.filter(a=>{return a!=arr[i]}),curr)
            curr.pop()
        }
    }
    
    
    let arr = [],counter = 0,res=''
    for(let i=1;i<=n;i++)arr.push(i)
    findPermutation(arr,[])
    return res
};

Approach) DFS (Depth First Search)

var getPermutation = function(n, k) {
    const list = Array.from({length:n}, (_,i)=>String(i+1));
    
    let counter = 0;
    const DFS = (arr)=>{
        if(arr.length===1) {
            counter++;
            if(counter===k) return arr[0];
            return;
        }
        let res = '';
        for(let i=0; i<arr.length; ++i) {
            const subStr = DFS( arr.filter((_,idx)=>idx!==i) );
            if(subStr) {
                res = arr[i]+subStr; 
                break;
            }
        }
        return res;
    }
    
    return DFS(list)
};

Approach) Recursion

    var getPermutation = function (n, k) {
      const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];  //array for remove used numbers
      let res = "";  // store result
      function getDigit(n, k) {  //a recusive funciton to get each row number
        if (n == 0) {
          return res;
        }
        let fac = 1;   
        let count = n;
        while (count-- > 1) {  //n - 1 fac
          fac *= count; 
        }
        let digit = k / fac | 0; //index of current row
        let left = k % fac;    // k mod current-digit left, for next recursion use
        res += nums[digit];   //res update
        nums.splice(digit, 1);  //remove used number
        return getDigit(n - 1, left);  //call recursive, pass n - 1 and mod left
      }
      getDigit(n, k - 1);
      return res;
    };

Approach) Mod Solution

var getPermutation = function(n, k) {
  const fib = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    if (i === 0) fib[i] = 1;
    else fib[i] = fib[i - 1] * i;
  }
  const nums = new Array(n).fill(1).map((_, i) => i + 1);
  // console.log(fib);
  // console.log(nums);
  let [tmp, tmpk, tmpn] = ["", k, n];
  while (nums.length > 0) {
    const next = Math.ceil(tmpk / fib[tmpn - 1]);
    const idx = Math.max(next - 1, 0);
    tmp += nums[idx];
    nums.splice(idx, 1);
    tmpk = fib[tmpn - 1] - (next * fib[tmpn - 1] - tmpk);
    tmpn--;
  }
  return tmp;
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem 60. Permutation Sequence

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!