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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Permutation Sequence

Number: 60

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Adobe, Uber, X

Problem Description

Given n and k, determine the kth permutation sequence of the set [1, 2, 3, …, n] when all permutations are listed in lexicographic order.

Key Insights

  • There are n! total permutations; each starting digit is repeated in blocks of size (n-1)!.
  • Adjust k to zero-based indexing to simplify calculations.
  • Use a list of candidates (numbers 1 to n) and iteratively determine the correct digit by leveraging factorial division.
  • Remove the chosen digit from the candidate list and update k accordingly.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case due to removal operations from the list. Space Complexity: O(n) for storing the candidate numbers and the factorial values.

Solution

We solve the problem using a greedy approach with factorial math. First, we compute the factorial values for numbers from 1 to n to know how many permutations start with a given digit. We maintain a list of candidate digits from 1 to n. For each position in the answer, we calculate the index by dividing the updated k (after converting to zero-based) by the factorial of the remaining digits. This index selects the digit from the candidates list. After selecting the digit, we remove it from the candidate list, update k (the remainder), and continue until all digits are used.

Code Solutions

def getPermutation(n, k):
    # List of numbers to get digits from
    numbers = [str(i) for i in range(1, n + 1)]
    
    # Pre-compute factorials up to n-1
    factorial = [1] * n
    for i in range(1, n):
        factorial[i] = factorial[i - 1] * i

    # Adjust k to zero-based index
    k -= 1
    
    permutation = []
    for i in range(n, 0, -1):
        # Determine the index for the current position
        index = k // factorial[i - 1]
        permutation.append(numbers.pop(index))
        # Update k for the next digit
        k %= factorial[i - 1]
    
    return ''.join(permutation)

# Example usage:
print(getPermutation(3, 3))  # Output should be "213"
print(getPermutation(4, 9))  # Output should be "2314"
← Back to All Questions