Table of Contents
Problem Statement
Permutation Sequence LeetCode Solution – 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
Test Case 1:
Input:
n = 3
k = 3
Output:
213
Explanation
213 is the third number in the permutation list having 3 digits.
Approach:
Brute Force would generate all n! permutations and then find the kth element.
We can optimize it using math.
Since we need to fix one position each time me need next we need to get permutations for (n-1)!
when n = 4, the list is 1, 2, 3, 4 and k = 18
the total number of permutations is
row1: 1 + {2, 3, 4}: 1234, 1243, 1324, 1342, 1423, 1432
==> 3! = 6 (factor) (from 0 to 5)
row2: 2 + {1, 3, 4}: 2134, 2143, 2314, 2341, 2413, 2431
==> 3! = 6 (from 6 to 11)
row3: 3 + {1, 2, 4}: 3! (from 12 to 17)
row4: 4 + {1, 2, 3}: 3! (from 18 to 23)
when k = 18, it means find the item from 0, then 17th is the permutation we want.
Since K =18 means we need to go to 17th index
so K–
Find out the number on each position
while i = n = 4
list: 1,2,3,4
index = (k – 1)/ (i – 1)! = 17/6 = 2. index 2 means it is row3 beginning with 3, then remove 3 from the list {1,2,3,4}, then the list becomes {1,2,4}. update k = (k-1) % 6 = 5.**** Add 3 to output.****
When n = 3
row 1
1,2,4
1,4,2
row 2
2,1,4
2,4,1
row 3
4,1,2
4,2,1
while i = n = 3, k = 5
list: 1, 2, 4
index = k / (i – 1)! = 5/2 = 2. index 2 means it is row3 beginning with 4, then remove 4 from the list {1, 2, 4}, then the list becomes {1, 4}. update k = k % 2 = 1. **** Add 4 to output.****
When n = 2
1,2
while i = n = 2, k = 1
list: 1,2
index = k/(i-1)! = 1/1 = 1. index 1 means it is row2 beginning with 2, then remove 2 from the list {1, 2}, then the list becomes {1}. update k = k % 1 = 0. Add 2 to the output.
When n = 1
1
while i = n = 1, k = 0
index = 0, index 0 means it is row1 beginning with 1. Add 1 to the output
Eventually, the output is 3421
Why Divide by Factorial?
Think about a simple case where you are finding the digits of a decimal number e.g. 4836. You can compute the rightmost place by dividing 4836 by 1 and then modulo 10 to get 6. Than 4836 by 10 modulo 10 to get 3, then 4836 by 100 modulo 10 to get 8, etc. We don’t need to change the number 4836 each time. Permutation case is similar but we use factorials instead of powers of 10 and modulus value changes.
n = 4, k = 9
Code for Permutation Sequence
Java Program
class Solution {
public String getPermutation(int n, int k) {
ArrayList<Integer> arr = new ArrayList<>();
int fact=1;
for(int i=1;i<n;i++){
fact=fact*i;
arr.add(i);
}
arr.add(n);
k=k-1;
String ans="";
while(true){
int i1 = k/fact;
int i2 = k%fact;
ans+=arr.get(i1);
arr.remove(i1);
k=i2;
if(arr.size()==0){
break;
}
fact=fact/arr.size();
}
return ans;
}
}C++ Program
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> nums;
string res;
int fact = 1;
for(int i=1;i<=n;i++){
fact *= i; // 1,2,6,24
nums.push_back(i); // [1] [1,2] [1,2,3] [1,2,3,4]
}
k = k - 1; // 0 base indexing 17-1 = 16
fact = fact/nums.size(); //24/4 = 6 (3! perm are more possible with remaining 3 elements as 1 out of 4 would be used)
while(true){
res += to_string(nums[k/fact]); // 16/6 = 2
nums.erase(nums.begin() + k/fact); // [1,2,4]
if(nums.size()==0){
return res;
}
k = k%fact; // 16%6=4
fact = fact/nums.size(); // 6/3 = 2 for coming elements we have arr of 2 ele only out of 3 , 1 would be contributing in res and 2! is 2 so fact is updated
}
return res;
}
};Complexity Analysis for Permutation Sequence LeetCode Solution
Time Complexity: O(n)
Space Complexity: O(n)