Permutation Sequence

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 k<sup>th</sup> 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"

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

def getPermutation(n: int, k: int) -> str:
    numbers = list(range(1, n + 1))
    factorial = [1] * (n + 1)
    for i in range(2, n + 1):
        factorial[i] = factorial[i - 1] * i
    
    k -= 1 # 0-indexed
    result = ""
    
    for i in range(n, 0, -1):
        index = k // factorial[i - 1]
        result += str(numbers[index])
        numbers.pop(index)
        k %= factorial[i - 1]
        
    return result

Explanation:

The problem requires us to find the kth permutation of the sequence [1, 2, 3, ..., n]. A brute-force approach would involve generating all n! permutations and then selecting the kth one. However, this is inefficient for larger values of n because generating all permutations has a time complexity of O(n!).

Instead, we can use a mathematical approach involving factorials to directly compute the kth permutation without generating all permutations. The key insight is that we can determine the first digit by dividing k by (n-1)!, which tells us which index in the sorted list of available numbers should be used for the first digit. Then we reduce k modulo (n-1)! and repeat the process for the remaining digits.

Optimal Solution:

1. Create a list of available numbers numbers = [1, 2, 3, ..., n]. Also, precompute factorials from 0 to n.
2. Decrement k by 1 to make it 0-indexed.
3. Iterate from n down to 1. In each iteration:
   • Calculate the index index = k // (i-1)!. The integer division determines the appropriate index.
   • Append the number at numbers[index] to the result.
   • Remove the number at numbers[index] from the numbers list.
   • Update k by taking the modulus: k = k % (i-1)!.
4. Return the resulting string.

Example:

For n = 4 and k = 9:

1. numbers = [1, 2, 3, 4]
2. factorial = [1, 1, 2, 6, 24]
3. k = 8 (0-indexed)

Loop:

• i = 4:
  • index = 8 // 6 = 1
  • result += str(numbers[1]) which is 2
  • numbers = [1, 3, 4]
  • k = 8 % 6 = 2
• i = 3:
  • index = 2 // 2 = 1
  • result += str(numbers[1]) which is 3
  • numbers = [1, 4]
  • k = 2 % 2 = 0
• i = 2:
  • index = 0 // 1 = 0
  • result += str(numbers[0]) which is 1
  • numbers = [4]
  • k = 0 % 1 = 0
• i = 1:
  • index = 0 // 1 = 0
  • result += str(numbers[0]) which is 4
  • numbers = []
  • k = 0 % 1 = 0

Final result: "2314"

Big(O) Runtime Analysis:

The dominant part of the algorithm is the loop that iterates n times. Inside the loop, we perform integer division, modulo operation, list indexing, and list removal. All these operations take O(1) time, except for numbers.pop(index) which takes O(n) time in worst case if the index is at the beginning of the list. However, the pop operation is performed at most n times in the whole algorithm, thus its contribution amortizes to O(n). The computation of factorials takes O(n) time. Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis:

The space complexity is determined by the storage required for the numbers list and the factorial list, each of which stores n+1 integers. Hence the space complexity is O(n).

Edge Cases:

1. Invalid Input:
   • If n is less than 1 or greater than 9, or if k is less than 1 or greater than n!, the input is invalid. An exception or error message should be returned.
2. k = 1:
   • When k is 1, the algorithm should return the smallest permutation, which is "123...n".
3. k = n!:
   • When k is n!, the algorithm should return the largest permutation, which is "n(n-1)(n-2)...1".
4. n = 1:
   • When n is 1, there is only one permutation "1" regardless of the value of k.

Code Implementation:

def getPermutation(n: int, k: int) -> str:
    numbers = list(range(1, n + 1))
    factorial = [1] * (n + 1)
    for i in range(2, n + 1):
        factorial[i] = factorial[i - 1] * i
    
    k -= 1 # 0-indexed
    result = ""
    
    for i in range(n, 0, -1):
        index = k // factorial[i - 1]
        result += str(numbers[index])
        numbers.pop(index)
        k %= factorial[i - 1]
        
    return result