60. Permutation Sequence

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!

 

Solutions

Solution: Math

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
const getPermutation = function (n, k) {
  const nums = new Array(n)
    .fill('')
    .map((_, index) => index + 1);
  const factorial = new Array(n + 1).fill(1);
  let result = '';

  for (let num = 1; num <= n; num++) {
    factorial[num] = num * factorial[num - 1];
  }
  k -= 1;
  for (let num = n - 1; num >= 0; num--) {
    const index = Math.floor(k / factorial[num]);

    result += nums[index];
    nums.splice(index, 1);
    k = k % factorial[num];
  }
  return result;
};