We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Permutation Sequence

Difficulty: Hard

Problem Description

Given a set of numbers from 1 to n, return the k-th permutation sequence of these numbers in lexicographical order.

Key Insights

  • The total number of permutations of n distinct numbers is n!.
  • The permutations can be divided into groups based on the first number, where each group contains (n-1)! permutations.
  • To find the k-th permutation, we can determine the first digit by calculating which group k falls into, and then recursively determine the subsequent digits.

Space and Time Complexity

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

Solution

We can use a factorial number system approach to solve this problem. The main idea is to find each digit of the permutation step by step. We maintain a list of numbers that are still available to be used and calculate the index of the first digit based on the factorial of the remaining numbers. This process is repeated until we construct the entire permutation.

  1. Compute the factorials for numbers from 0 to n-1.
  2. Create a list of numbers to represent the set [1, 2, ..., n].
  3. Adjust k to be zero-indexed (k - 1).
  4. For each position in the result:
    • Determine the index of the next digit using k divided by (n-1)!.
    • Update k to find the next digit's index in the next iteration.
    • Remove the used digit from the list of available numbers.
  5. Join the result list to form the final permutation string.

Code Solutions

def getPermutation(n: int, k: int) -> str:
    # Precompute factorials
    factorials = [1] * n
    for i in range(1, n):
        factorials[i] = factorials[i - 1] * i
    
    # Create a list of numbers to get permutations from
    numbers = list(range(1, n + 1))
    
    # Adjust k to be zero-indexed
    k -= 1
    result = []
    
    # Build the k-th permutation
    for i in range(n):
        index = k // factorials[n - 1 - i]
        result.append(str(numbers[index]))
        numbers.pop(index)
        k %= factorials[n - 1 - i]
    
    return ''.join(result)
← Back to All Questions