LeetCode 60: Permutation Sequence Solution in Python Explained

Problem Statement

LeetCode 60, Permutation Sequence, is a medium-level problem where you’re given two integers n and k. Your task is to return the (k)-th permutation of the sequence [1, 2, ..., n] in lexicographical order. The permutations are numbered from 1 to (n!), and you need to find the specific (k)-th permutation as a string.

Constraints

1 <= n <= 9: Length of sequence is between 1 and 9.
1 <= k <= n!: \(k\) is a valid permutation index.

Example

Input: n = 3, k = 3
Output: "213"
Explanation: Permutations in order:
1. "123"
2. "132"
3. "213" <- 3rd permutation
4. "231"
5. "312"
6. "321"

Input: n = 4, k = 9
Output: "2314"
Explanation: 9th permutation of [1,2,3,4].

Input: n = 1, k = 1
Output: "1"
Explanation: Only permutation is "1".

Understanding the Problem

How do you solve LeetCode 60: Permutation Sequence in Python? For n = 3 and k = 3, find the 3rd permutation of [1,2,3], which is "213". Generating all (n!) permutations and picking the (k)-th is inefficient (O(n!)), so we need a smarter approach. We’ll explore two solutions: a Mathematical Factorial Approach (optimal and primary) and an Alternative with Iterative Permutation (more intuitive but slower). The factorial method uses math to compute the permutation in O(n^2) time.

Solution 1: Mathematical Factorial Approach (Primary)

Explanation

Use factorials to determine each digit of the permutation. For (n) numbers, there are ((n-1)!) permutations starting with each number. Divide (k-1) by ((n-1)!) to find the index of the first digit, remove it, and repeat with the remaining numbers and updated (k).

Here’s a flow for (n = 3, k = 3):

Numbers: [1,2,3], k = 2 (k-1)
(2)! = 2, k = 2, index = 1 -> "2", remaining = [1,3], k = 0
(1)! = 1, k = 0, index = 0 -> "1", remaining = [3], k = 0
(0)! = 1, k = 0, index = 0 -> "3"
Result: "213"

Initialize Numbers and Factorials.

List of numbers [1,2,...,n], precompute factorials.

Compute Digits.

Use \(k-1\) to find each digit’s index, adjust \(k\).

Build String.

Append digits, remove used numbers.

Return Result.

Step-by-Step Example

Example 1: n = 3, k = 3

We need "213".

Goal: Find 3rd permutation of [1,2,3].
Result for Reference: "213".
Start: n = 3, k = 3, numbers = [1,2,3], result = "", k = 2 (k-1).
Step 1: n = 3, factorial = (2)! = 2.

Index = k // 2 = 2 // 2 = 1, digit = numbers[1] = 2.
result = "2", remove 2, numbers = [1,3], k = k % 2 = 0.

Step 2: n = 2, factorial = (1)! = 1.

Index = 0 // 1 = 0, digit = numbers[0] = 1.
result = "21", remove 1, numbers = [3], k = 0 % 1 = 0.

Step 3: n = 1, factorial = (0)! = 1.

Index = 0 // 1 = 0, digit = numbers[0] = 3.
result = "213", numbers = [].

Finish: Return "213".

Example 2: n = 4, k = 9

We need "2314".

Start: numbers = [1,2,3,4], k = 8 (k-1).
Step 1: (3)! = 6, index = 8 // 6 = 1, digit = 2, k = 8 % 6 = 2.

result = "2", numbers = [1,3,4].

Step 2: (2)! = 2, index = 2 // 2 = 1, digit = 3, k = 2 % 2 = 0.

result = "23", numbers = [1,4].

Step 3: (1)! = 1, index = 0 // 1 = 0, digit = 1, k = 0.

result = "231", numbers = [4].

Step 4: (0)! = 1, index = 0, digit = 4.

result = "2314", numbers = [].

Finish: Return "2314".

How the Code Works (Mathematical Factorial)

Here’s the Python code with line-by-line explanation:

def getPermutation(n: int, k: int) -> str:
    # Line 1: Initialize numbers and factorials
    numbers = list(range(1, n + 1))
    factorials = [1] * (n + 1)
    for i in range(1, n):
        factorials[i] = factorials[i-1] * i

    # Line 2: Adjust k to 0-based index
    k -= 1

    # Line 3: Build permutation
    result = []
    for i in range(n-1, -1, -1):
        if i == 0:
            result.append(str(numbers[0]))
            break
        # Line 4: Calculate index and digit
        index = k // factorials[i]
        k = k % factorials[i]
        digit = numbers[index]
        # Line 5: Add digit and remove from numbers
        result.append(str(digit))
        numbers.pop(index)

    # Line 6: Return permutation as string
    return ''.join(result)

Alternative: Iterative Permutation Approach

Explanation

Generate permutations iteratively using the "next permutation" algorithm (like LeetCode 31), starting from [1,2,...,n] and iterating until the (k)-th permutation is reached. This is less efficient but mimics the lexicographical order directly.

Initialize Sequence.
Generate Next Permutation.

Swap and reverse to get next in order.

3. Iterate (k-1) Times. 4. Return Result.

Step-by-Step Example (Alternative)

For (n = 3, k = 3):

Start: nums = [1,2,3], k = 3.
Step 1: 1st: [1,2,3].
Step 2: 2nd: [1,3,2] (swap 2,3, reverse nothing).
Step 3: 3rd: [2,1,3] (swap 1,3, reverse [3,2]).
Finish: Return "213".

How the Code Works (Iterative Permutation)

def getPermutationIter(n: int, k: int) -> str:
    # Line 1: Initialize sequence
    nums = list(range(1, n + 1))

    # Line 2: Generate k-1 next permutations
    for _ in range(k - 1):
        # Line 3: Find first decreasing element from right
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        # Line 4: Find number to swap
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        # Line 5: Swap
        nums[i], nums[j] = nums[j], nums[i]
        # Line 6: Reverse after i
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    # Line 7: Return as string
    return ''.join(map(str, nums))

Complexity

Mathematical Factorial:

Time: O(n^2) – n iterations, O(n) for list removal.
Space: O(n) – Numbers list and factorials.

Iterative Permutation:

Time: O(k * n) – k iterations, O(n) per next permutation, up to O(n * n!).
Space: O(n) – Store sequence.

Efficiency Notes

Mathematical Factorial is O(n^2) time and O(n) space, optimal for LeetCode 60 as it avoids generating all permutations. Iterative Permutation is O(k * n) time, potentially O(n * n!), making it impractical for large (k), but it’s a clear alternative.

Key Insights

Tips to master LeetCode 60:

Factorial Math: Use \((n-1)!\) to find each digit.
Index Adjustment: \(k-1\) for 0-based indexing.
Efficient Build: Avoid full permutation generation.

Additional Example

For (n = 2, k = 2):

Goal: "21".
Factorial: [1,2], k-1=1, (1)! = 1, index = 1, "2", "1" -> "21".
Result: "21".

Edge Cases

\(n = 1, k = 1\): "1".
\(n = 9, k = 362880\): Last permutation of [1,2,3,4,5,6,7,8,9].
\(n = 2, k = 1\): "12".

Final Thoughts

The Mathematical Factorial solution is a brilliant pick for LeetCode 60 in Python—fast, clever, and math-driven. For a related challenge, try LeetCode 59: Spiral Matrix II to switch to matrix generation! Ready to permute? Solve LeetCode 60 on LeetCode now and test it with (n=3, k=3) or (n=4, k=9) to master permutation sequences. Dive in and sequence it up!