Last updated on March 2nd, 2025 at 05:08 pm
Here, we see a Permutation Sequence LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Backtracking, Math
Companies
Level of Question
Hard
Permutation Sequence LeetCode Solution
Table of Contents
1. 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:
"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"
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Mathematical Permutations”. The code leverages factorials to calculate the k-th permutation of a sequence of numbers without generating all permutations explicitly. This is a direct application of combinatorics and mathematical reasoning.
3. Code Implementation in Different Languages
3.1 Permutation Sequence 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;
}
};
3.2 Permutation Sequence 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.3 Permutation Sequence 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;
};
3.4 Permutation Sequence 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n²) | O(n) |
| Java | O(n²) | O(n) |
| JavaScript | O(n²) | O(n) |
| Python | O(n²) | O(n) |
- The code efficiently calculates the k-th permutation using factorials and avoids generating all permutations.
- The time complexity is O(n²) due to the repeated removal of elements from the list.
- The space complexity is O(n) for storing the factorials, numbers, and result.