Permutation Sequence - Leetcode Solution

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:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3 Output: "213"

Example 2:

Input: n = 4, k = 9 Output: "2314"

Solution:

In this problem, we need to find the kth permutation sequence of [1,2,3,...,n]. We can approach this problem by finding the digits from left to right.

Let's consider an example: n=4, k=9. The total number of permutations of [1,2,3,4] is 4! = 24, which means that there are 24 possible sequences. The first digit can be selected from [1,2,3,4], which means that there are 4 possible options (i.e, we have 4 choices for the first digit). If we fix the first digit, we are left with (n-1)! possible permutations for the remaining digits. Therefore, there are (4-1)! = 6 possible permutations for the remaining three digits. Similarly, there are (3-1)! = 2 possible permutations for the remaining two digits and 1 possible permutation for the last digit.

We can use this approach to find the kth permutation sequence. We start by finding the index of the first digit in the sequence. The index is given by (k-1)/(n-1)!, which gives the number of blocks of (n-1)! permutations that we need to skip to reach the kth sequence. We subtract 1 from this index to get the index of the actual digit in the list. We then remove this digit from the list and repeat the process for the remaining digits.

Here is the detailed algorithm:

1. Create a list of digits from 1 to n.
2. Create a factorials list, which stores the factorial of integers from 0 to n.
3. Decrement k by 1 (0-based indexing).
4. Create an empty result string.
5. Repeat n times: a. Find the index of the first digit in the list using the formula: (k // factorials[n-1]). b. Add the digit at the index to the result string. c. Remove the digit from the list. d. Update k using the formula: k = k % factorials[n-1]. e. Decrement n by 1.
6. Return the result string.

Here is the Python code for the above algorithm:

class Solution: def getPermutation(self, n: int, k: int) -> str: nums = [str(i) for i in range(1, n+1)] factorials = [1] for i in range(1, n+1): factorials.append(factorials[-1] * i)

    k -= 1
    result = ""
    for i in range(n, 0, -1):
        index = k // factorials[i-1]
        result += nums[index]
        nums.pop(index)
        k %= factorials[i-1]
    
    return result

Time Complexity: O(n^2) Space Complexity: O(n)

1