Leetcode 60. Permutation Sequence
Problem Explanation
Given a positive integer n
upto 9
, we need to return the kth
permutation sequence of all the permutations of 1
to n
.
For instance, for n = 3
, the permutations would be: 123
, 132
, 213
, 231
, 312
, 321
. If k=4
, the 4th
permutation sequence is 231
.
There are total n!
permutations for n
. Our task is to find the kth
permutation (in lexicographically sorted order) amongst all possible permutations.
Approach
To solve this problem, we implement the following approach:
-
Start by initializing an array of
n
integers wherein each integeri
takes the valuei+1
. -
Additionally, create an array
fact
that holds the factorial of integers0
ton
. -
Begin iterating from
n-1
to0
. For each indexi
, computej = k / fact[i]
andk = k % fact[i]
. -
Append the
jth
number fromnums
toans
, remove the number fromnums
and continue the process. -
Finally, the string
ans
holds thekth
permutation.
Python Solution
1 2python 3class Solution: 4 def getPermutation(self, n: int, k: int) -> str: 5 nums = list(range(1, n+1)) # List of numbers 1 to n 6 fact = [1]*(n+1) # List to store factorials of numbers 7 8 for i in range(1, n+1): 9 fact[i] = fact[i-1] * i 10 11 k -= 1 # converting k to 0-based index 12 13 ans = "" 14 for i in range(n, 0, -1): 15 j = k // fact[i-1] # finding the index of next number 16 k %= fact[i-1] # updating k 17 ans += str(nums[j]) # appending the number to the answer 18 nums.pop(j) # remove the number from the list 19 20 return ans
Java Solution
1 2java 3class Solution { 4 public String getPermutation(int n, int k) { 5 List<Integer> nums = new ArrayList<Integer>(); 6 int[] fact = new int[n + 1]; 7 StringBuilder sb = new StringBuilder(); 8 9 int sum = 1; 10 fact[0] = 1; 11 for(int i = 1; i <= n; i++) { 12 nums.add(i); 13 sum *= i; 14 fact[i] = sum; 15 } 16 k--; 17 18 for (int i = 1; i <= n; i++) { 19 int j = k / fact[n - i]; 20 k = k % fact[n - i]; 21 sb.append(nums.get(j)); 22 nums.remove(j); 23 } 24 return sb.toString(); 25 } 26}
C++ Solution
1 2cpp 3class Solution { 4public: 5 string getPermutation(int n, int k) { 6 string res = ""; 7 vector<int> num(n); 8 vector<int> fact(n+1, 1); 9 10 for(int i = 0; i < n; i++) num[i] = i+1; 11 for(int i = 1; i <= n; i++) fact[i] = i*fact[i-1]; 12 13 k--; 14 for(int i = n; i >= 1; i--) { 15 int j = k / fact[i-1]; 16 k %= fact[i-1]; 17 res.push_back(num[j] + '0'); 18 num.erase(num.begin() + j); 19 } 20 return res; 21 } 22};
JavaScript Solution
1 2js 3var getPermutation = function(n, k) { 4 k--; // convert to zero indexed 5 const nums = Array.from({length: n}, (_, index) => index + 1); 6 const fact = [1]; 7 for (let i = 1; i <= n; i++) 8 fact[i] = i * fact[i - 1]; 9 10 let ans = ''; 11 for (let i = n - 1; i >= 0; i--) { 12 const idx = Math.floor(k / fact[i]); 13 k %= fact[i]; 14 15 ans += nums[idx]; 16 nums.splice(idx, 1); 17 } 18 return ans; 19};
C# Solution
1 2csharp 3public class Solution { 4 public string GetPermutation(int n, int k) { 5 k--; 6 List<int> nums = new List<int>(); 7 int[] fact = new int[n+1]; 8 fact[0] = 1; 9 StringBuilder sb = new StringBuilder(); 10 11 for(int i = 1; i <= n; i++) 12 { 13 nums.Add(i); 14 fact[i] = i*fact[i-1]; 15 } 16 17 for(int i = n; i >= 1; i--) 18 { 19 int idx = k / fact[i-1]; 20 k %= fact[i-1]; 21 sb.Append(nums[idx]); 22 nums.RemoveAt(idx); 23 } 24 25 return sb.ToString(); 26 } 27}
The getPermutation()
function implemented in all the above solutions follows the same approach to generate the kth permutation sequence. They calculate the factorials using dynamic programming, calculate the next index, and append the corresponding number to the resultant string after each iteration.This problem can be solved with the help of fundamental counting principle.
Fundamentally, this problem resolves around selecting the starting number of every available digit. So, the selection of starting digit depends on whether the remaining permutations (factorial of remaining digits) is greater than the desired k or not. If it is greater, then we have the correct starting digit otherwise, we increment the starting digit.
Let's discuss solutions in detail:
Solutions
Python
In Python, we first calculate the factorial of all numbers to n
and store them in a list. Then we create a list of number to n
. We then start iterating from n-1 down to 0 (both inclusive) and for each i
, we calculate the index idx
by k
divide the fact[i]
, and ans
can append this element. After the process, we update k
to k
modulus fact[i]
.
1 2python 3class Solution: 4 def getPermutation(self, n: int, k: int) -> str: 5 factorial = [1] 6 for i in range(1, n+1): # Using xrange to increase space efficiency 7 factorial.append(factorial[-1]*i) 8 res, k, nums = [], k-1, [i for i in range(1, n+1)] 9 for i in range(n, 0, -1): 10 idx = k // factorial[i-1] 11 k %= factorial[i-1] 12 res.append(str(nums[idx])) 13 nums.pop(idx) 14 return ''.join(res)
Java
In Java, we use the ArrayList to contain the integer numbers and then make use of StringBuilder to add numbers in the result string. We then start iterating from i
being equal to n
till 1 and for each i
, calculate the index idx
by k
divided by fact[n-i]
, update k
to k
modulus fact[n-i]
and add nums.get(idx)
to the StringBuilder
. Also, remove nums.get(idx)
from nums
.
1 2java 3 4class Solution { 5 public String getPermutation(int n, int k) { 6 List<Integer> nums = new ArrayList<>(); 7 int[] fact = new int[n+1]; 8 fact[0] = 1; 9 StringBuilder sb = new StringBuilder(); 10 11 for(int i = 1; i <= n; i++){ 12 fact[i] = fact[i-1]* i; 13 nums.add(i); 14 } 15 16 k--; 17 18 for(int i = n; i > 0; i--){ 19 int idx = k / fact[i-1]; 20 k %= fact[i - 1]; 21 sb.append(nums.get(idx)); 22 nums.remove(idx); 23 } 24 25 return sb.toString(); 26 } 27}
The above solutions work in O(n)
time complexity.
So, the next time you come across similar permutation sequence problems, remember this mathematical property to quickly find the desired permutation. Also, remember to convert k
to zero-indexed which can save you from off-by-one errors that are easy to commit in these types of problems.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.