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.

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 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!
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.