Permutation Sequence Leetcode Solution

In this post, we are going to solve the Permutation Sequence Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Table of Contents

Problem

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 k^th 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!

Now, let’s see the leetcode solution of Permutation Sequence Leetcode Solution.

Permutation Sequence Leetcode Solution in Python

class Solution:
  def getPermutation(self, n: int, k: int) -> str:
    ans = ''
    nums = [i + 1 for i in range(n)]
    factorial = [1] * (n + 1)  # factorial[i] := i!

    for i in range(2, n + 1):
      factorial[i] = factorial[i - 1] * i

    k -= 1  # 0-indexed

    for i in reversed(range(n)):
      j = k // factorial[i]
      k %= factorial[i]
      ans += str(nums[j])
      nums.pop(j)

    return ans

Permutation Sequence Leetcode Solution in CPP

class Solution {
 public:
  string getPermutation(int n, int k) {
    string ans;
    vector<int> nums(n);
    vector<int> factorial(n + 1, 1);  // factorial[i] := i!

    iota(begin(nums), end(nums), 1);

    for (int i = 2; i <= n; ++i)
      factorial[i] = factorial[i - 1] * i;

    --k;  // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      const int j = k / factorial[i];
      k %= factorial[i];
      ans += to_string(nums[j]);
      nums.erase(begin(nums) + j);
    }

    return ans;
  }
};

Permutation Sequence Leetcode Solution in Java

class Solution {
  public String getPermutation(int n, int k) {
    StringBuilder sb = new StringBuilder();
    List<Integer> nums = new ArrayList<>();
    int[] factorial = new int[n + 1]; // factorial[i] := i!

    for (int i = 1; i <= n; ++i)
      nums.add(i);

    Arrays.fill(factorial, 1);
    for (int i = 2; i <= n; ++i)
      factorial[i] = factorial[i - 1] * i;

    --k; // 0-indexed

    for (int i = n - 1; i >= 0; --i) {
      final int j = k / factorial[i];
      k %= factorial[i];
      sb.append(nums.get(j));
      nums.remove(j);
    }

    return sb.toString();
  }
}

Note: This problem Permutation Sequence is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

NEXT: Rotate List Leetcode Solution