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:

1. Start by initializing an array of n integers wherein each integer i takes the value i+1.

2. Additionally, create an array fact that holds the factorial of integers 0 to n.

3. Begin iterating from n-1 to 0. For each index i, compute j = k / fact[i] and k = k % fact[i].

4. Append the jth number from nums to ans, remove the number from nums and continue the process.

5. Finally, the string ans holds the kth 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.