60. Permutation Sequence

Problem Statement

link: https://leetcode.com/problems/permutation-sequence/ https://leetcode.cn/problems/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:

“123” “132” “213” “231” “312” “321” Given n and k, return the kth permutation sequence.

Example:

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

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

Input: n = 3, k = 1 Output: "123"

Solution Approach

The solution leverages the factorial properties of permutations to determine the position of each number in the sequence.

Algorithm

1. Factorial and Number Array Initialization: First, generate two arrays: one (f) to store the factorials from 1 to n, and another (nums) to store numbers from 1 to n.
2. Calculation of Position: For each number from n down to 1, calculate the position (index) of the number in the nums array using the formula: index = k // f[i - 1], where f is the factorial array. Append the number at the calculated position to the result and remove it from the nums array.
3. K Value Update: Update k for the next iteration using the formula: k %= f[i - 1]. This algorithm constructs the permutation string by calculating the position of each digit one-by-one.

Implement

    class Solution:
    def getPermutation(self, n: int, k: int) -> str:
      f, nums = [1], []
      for i in range(1, n + 1):
          f.append(f[i - 1] * i)
          nums.append(i)   
      res = []
      k -= 1 
      for i in range(n, 0, -1):
          index = k // f[i - 1]  # Use integer division to get the index
          res.append(nums.pop(index))
          k %= f[i - 1]  # Update k for the next iteration

      return ''.join(map(str, res))

    
    

Twitter  facebook  Email