LeetCode Problem 60

Difficulty: 🔴 Hard
Topics: Math, Recursion

Solution

LeetCode 60, Permutation Sequence

Problem Understanding

The problem gives us the numbers from 1 to n, and asks us to find the kth permutation when all possible permutations are ordered lexicographically.

For example, when n = 3, the numbers are:

[1, 2, 3]

All permutations in sorted order are:

123
132
213
231
312
321

If k = 3, the answer is "213" because it is the third permutation in this ordering.

The important detail is that permutations are ordered lexicographically, which means they are sorted like strings or dictionary words.

The input consists of:

• n, the number of digits from 1 to n
• k, the position of the desired permutation, using 1-based indexing

The output is a string representing the kth permutation.

The constraints are small:

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

Since n is at most 9, the largest number of permutations is:

9! = 362880

This is small enough that brute force is technically possible, but still inefficient compared to a direct mathematical construction.

Several edge cases are important:

• k = 1, we should return the smallest permutation
• k = n!, we should return the largest permutation
• n = 1, there is only one possible permutation
• Correct handling of 1-based indexing is critical, many implementations fail because factorial indexing naturally works with 0-based indices

Approaches

Brute Force Approach

A straightforward solution is to generate every permutation of the numbers 1 through n, sort them lexicographically, and then return the kth one.

This works because generating all permutations guarantees that the target permutation will appear somewhere in the list.

For example, with n = 4, we could:

1. Generate all 24 permutations
2. Sort them
3. Return the permutation at index k - 1

While correct, this approach becomes inefficient because the number of permutations grows factorially.

The time complexity becomes very large:

O(n! * n)

This happens because:

• There are n! permutations
• Each permutation contains n characters
• Sorting also adds additional overhead

Although n <= 9 makes brute force technically feasible, it is not an elegant or optimal solution.

Optimal Approach, Factorial Number System

The key insight is that permutations follow a predictable block structure.

Suppose n = 4.

There are:

4! = 24

total permutations.

If we fix the first digit:

• All permutations starting with 1 occupy the first 3! = 6 positions
• All permutations starting with 2 occupy the next 6
• All permutations starting with 3 occupy the next 6
• All permutations starting with 4 occupy the final 6

This means we can determine each digit directly using factorials, without generating all permutations.

At every step:

• Compute how many permutations each remaining digit contributes
• Determine which block contains the target permutation
• Select that digit
• Remove it from the available digits
• Continue with the remaining positions

This technique is essentially converting k into a factorial-based positional system.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * n)	O(n! * n)	Generates every permutation explicitly
Optimal	O(n²)	O(n)	Constructs the answer directly using factorial math

Algorithm Walkthrough

Optimal Algorithm

1. Create a list of available digits from 1 to n.

For example, if n = 4:

digits = [1, 2, 3, 4]

These are the numbers we can still place into the permutation. 2. Precompute factorial values.

We need factorials because permutations are grouped into blocks of size:

(remaining_digits - 1)!

For n = 4:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24

3. Convert k from 1-based indexing to 0-based indexing.

This is extremely important.

Factorial indexing works naturally with zero indexing.

So we do:

k = k - 1

4. Determine the first digit.

Suppose we have n = 4 and k = 9.

After converting to zero indexing:

k = 8

Each first-digit block contains:

3! = 6

permutations.

Compute:

index = k // 6 = 1

This means we choose the digit at index 1 in:

[1, 2, 3, 4]

which is 2. 5. Remove the chosen digit.

After choosing 2:

digits = [1, 3, 4]

6. Update k.

We only care about the position inside the selected block.

Compute:

k = k % 6

which becomes:

k = 2

7. Repeat the process for the remaining positions.

Now each block size becomes:

2! = 2

Continue selecting digits until no digits remain. 8. Join all selected digits into the final string.

Why it works

The algorithm works because lexicographically ordered permutations are partitioned into equally sized blocks determined by factorials.

For any position:

• Each remaining digit contributes exactly (remaining_positions)! permutations
• Integer division identifies which block contains the target permutation
• Modulo identifies the relative position inside that block

By repeatedly narrowing the search space, the algorithm constructs the exact kth permutation directly without generating unnecessary permutations.

Python Solution

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # Precompute factorials
        factorial = [1] * (n + 1)
        
        for i in range(1, n + 1):
            factorial[i] = factorial[i - 1] * i
        
        # Available digits
        digits = [str(i) for i in range(1, n + 1)]
        
        # Convert to 0-based indexing
        k -= 1
        
        result = []
        
        # Build permutation
        for remaining in range(n, 0, -1):
            block_size = factorial[remaining - 1]
            
            index = k // block_size
            
            result.append(digits[index])
            
            digits.pop(index)
            
            k %= block_size
        
        return "".join(result)

The implementation begins by precomputing factorial values. This allows constant-time lookup of block sizes during permutation construction.

The digits list stores all currently available numbers that have not yet been used in the permutation.

The conversion:

k -= 1

is essential because factorial block indexing is naturally zero based.

The main loop processes one digit position at a time. For each position:

• block_size determines how many permutations belong to each candidate digit
• index identifies which digit block contains the target permutation
• The chosen digit is appended to the result
• The digit is removed so it cannot be reused
• k is reduced to the offset within the chosen block

Finally, all digits are joined into the answer string.

Go Solution

func getPermutation(n int, k int) string {
	// Precompute factorials
	factorial := make([]int, n+1)
	factorial[0] = 1

	for i := 1; i <= n; i++ {
		factorial[i] = factorial[i-1] * i
	}

	// Available digits
	digits := make([]byte, n)

	for i := 0; i < n; i++ {
		digits[i] = byte('1' + i)
	}

	// Convert to 0-based indexing
	k--

	result := make([]byte, 0, n)

	// Build permutation
	for remaining := n; remaining >= 1; remaining-- {
		blockSize := factorial[remaining-1]

		index := k / blockSize

		result = append(result, digits[index])

		// Remove used digit
		digits = append(digits[:index], digits[index+1:]...)

		k %= blockSize
	}

	return string(result)
}

The Go implementation follows the same logic as the Python solution.

A []byte slice is used instead of strings because bytes are efficient for character manipulation in Go.

Removing a digit uses slice concatenation:

digits = append(digits[:index], digits[index+1:]...)

Since n <= 9, integer overflow is not a concern because 9! easily fits inside a standard Go int.

Worked Examples

Example 1

Input: n = 3, k = 3

After converting to zero indexing:

k = 2

Available digits:

[1, 2, 3]

Factorials:

0! = 1
1! = 1
2! = 2
3! = 6

Step	Remaining Digits	Block Size	k	Index	Chosen Digit	Result
1	[1,2,3]	2	2	1	2	"2"
2	[1,3]	1	0	0	1	"21"
3	[3]	1	0	0	3	"213"

Final answer:

"213"

Example 2

Input: n = 4, k = 9

Convert to zero indexing:

k = 8

Step	Remaining Digits	Block Size	k	Index	Chosen Digit	Result
1	[1,2,3,4]	6	8	1	2	"2"
2	[1,3,4]	2	2	1	3	"23"
3	[1,4]	1	0	0	1	"231"
4	[4]	1	0	0	4	"2314"

Final answer:

"2314"

Example 3

Input: n = 3, k = 1

Convert to zero indexing:

k = 0

Step	Remaining Digits	Block Size	k	Index	Chosen Digit	Result
1	[1,2,3]	2	0	0	1	"1"
2	[2,3]	1	0	0	2	"12"
3	[3]	1	0	0	3	"123"

Final answer:

"123"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Removing elements from a list or slice costs O(n), repeated n times
Space	O(n)	Stores factorials, available digits, and result

The algorithm iterates exactly n times. Each iteration may remove an element from the middle of a list, which costs linear time due to shifting elements. Therefore, the total time complexity becomes:

O(n + (n-1) + (n-2) + ...)
= O(n²)

Since n <= 9, this is extremely efficient in practice.

Test Cases

solution = Solution()

assert solution.getPermutation(3, 3) == "213"      # Example 1
assert solution.getPermutation(4, 9) == "2314"     # Example 2
assert solution.getPermutation(3, 1) == "123"      # Example 3

assert solution.getPermutation(1, 1) == "1"        # Smallest possible input
assert solution.getPermutation(2, 2) == "21"       # Last permutation for n=2

assert solution.getPermutation(3, 6) == "321"      # Largest permutation for n=3
assert solution.getPermutation(4, 24) == "4321"    # Largest permutation for n=4

assert solution.getPermutation(4, 1) == "1234"     # First permutation
assert solution.getPermutation(5, 120) == "54321"  # Largest permutation for n=5

assert solution.getPermutation(5, 42) == "24531"   # Mid-range permutation
assert solution.getPermutation(6, 400) == "425361" # Larger input stress case

Test	Why
n=3, k=3	Validates standard example
n=4, k=9	Tests multi-level factorial selection
n=3, k=1	Ensures first permutation works
n=1, k=1	Smallest valid input
n=2, k=2	Small permutation boundary
n=3, k=6	Tests final permutation
n=4, k=24	Verifies handling of n! boundary
n=4, k=1	Confirms smallest lexicographic result
n=5, k=120	Tests largest permutation for larger n
n=5, k=42	Mid-range correctness check
n=6, k=400	Stress test with larger factorial indexing

Edge Cases

Edge Case 1, n = 1

When there is only one number, only one permutation exists.

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

Some implementations incorrectly assume multiple factorial levels exist and may produce indexing errors. This implementation handles the case naturally because the loop runs once and selects the only available digit.

Edge Case 2, k = 1

The first permutation should always be the lexicographically smallest arrangement.

For example:

n = 4, k = 1

should produce:

"1234"

After converting to zero indexing, k = 0, so every block selection chooses index 0. The algorithm therefore always picks the smallest remaining digit.

Edge Case 3, k = n!

The final permutation should always be the lexicographically largest arrangement.

For example:

n = 4, k = 24

should produce:

"4321"

This case is easy to mishandle if indexing is not converted properly. Because the implementation converts k to zero indexing before processing, the factorial divisions correctly select the final block at every level.

Edge Case 4, Off-by-One Errors

This problem is especially prone to indexing mistakes because:

• Input k is 1-based
• Factorial grouping logic is naturally 0-based

Without:

k -= 1

the algorithm would consistently choose incorrect blocks.

The implementation explicitly converts k before processing, eliminating this issue entirely.