LeetCode 60: Permutation Sequence

Problem Restatement

We are given two integers, n and k.

The set is:

[1, 2, 3, ..., n]

This set has n! unique permutations.

If we list all permutations in sorted order, we need to return the kth permutation as a string.

The official constraints are 1 <= n <= 9 and 1 <= k <= n!.

Input and Output

Function shape:

def getPermutation(n: int, k: int) -> str:
    ...

Examples

For:

n = 3
k = 3

The permutations in order are:

1. 123
2. 132
3. 213
4. 231
5. 312
6. 321

The 3rd permutation is:

"213"

For:

n = 4
k = 9

The answer is:

"2314"

For:

n = 3
k = 1

The answer is:

"123"

First Thought: Generate All Permutations

A direct solution is:

1. Generate all permutations of [1, 2, ..., n].
2. Sort them.
3. Return the kth one.

This works for small n, but it does unnecessary work.

There are n! permutations. Even though n <= 9, generating every permutation is still much heavier than needed.

We only need one permutation.

Key Insight

Permutations are grouped by their first digit.

For n = 4, the digits are:

[1, 2, 3, 4]

If the first digit is fixed as 1, the remaining digits [2, 3, 4] can be arranged in:

3! = 6

ways.

So the first 6 permutations start with 1.

The next 6 permutations start with 2.

The next 6 start with 3.

The next 6 start with 4.

This means we can use factorials to skip whole blocks of permutations.

For each position:

1. Compute how many permutations each candidate digit controls.
2. Use k to choose the correct block.
3. Remove that digit.
4. Continue with the remaining digits.

Convert k to Zero-Based Index

The problem gives k as 1-indexed.

That means:

k = 1 means the first permutation
k = 2 means the second permutation

Array indices are easier with zero-based indexing, so we convert:

k -= 1

Now:

k = 0 means the first permutation
k = 1 means the second permutation

This makes the block calculation cleaner.

Walkthrough

Use:

n = 4
k = 9

First convert:

k = 8

Available digits:

[1, 2, 3, 4]

For the first position, each starting digit has:

3! = 6

permutations.

Compute:

index = 8 // 6 = 1

So we choose the digit at index 1, which is 2.

Result so far:

"2"

Update:

k = 8 % 6 = 2

Remaining digits:

[1, 3, 4]

For the second position, each digit controls:

2! = 2

permutations.

Compute:

index = 2 // 2 = 1

Choose digit at index 1, which is 3.

Result:

"23"

Update:

k = 2 % 2 = 0

Remaining digits:

[1, 4]

For the third position, each digit controls:

1! = 1

Compute:

index = 0 // 1 = 0

Choose 1.

Result:

"231"

Remaining digit:

[4]

Final result:

"2314"

Algorithm

Create a list of available digits:

digits = ["1", "2", ..., str(n)]

Precompute factorials:

fact[i] = i!

Convert k to zero-based:

k -= 1

Then for each remaining position:

1. Let block_size = fact[remaining_count - 1].
2. Choose index = k // block_size.
3. Append digits[index] to the answer.
4. Remove that digit from digits.
5. Update k = k % block_size.

Return the joined answer.

Correctness

At any position, suppose there are m remaining digits. If we fix one digit at the current position, the remaining m - 1 digits can be arranged in (m - 1)! ways.

Therefore, the sorted permutation list is divided into blocks of size (m - 1)!, where each block corresponds to one possible current digit.

The value k // block_size identifies exactly which block contains the desired permutation. Choosing the digit at that index selects the correct current digit.

Then k % block_size gives the rank of the desired permutation inside that chosen block. The same reasoning applies recursively to the remaining positions.

Since the algorithm repeats this block selection until every digit is chosen, it constructs exactly the requested permutation.

Complexity

With n <= 9, this is easily within the limit.

Implementation

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        digits = [str(i) for i in range(1, n + 1)]

        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i

        k -= 1

        ans = []

        for remaining in range(n, 0, -1):
            block_size = fact[remaining - 1]
            index = k // block_size

            ans.append(digits.pop(index))

            k %= block_size

        return "".join(ans)

Code Explanation

We create the available digits:

digits = [str(i) for i in range(1, n + 1)]

For n = 4, this gives:

["1", "2", "3", "4"]

Then we precompute factorials:

fact = [1] * (n + 1)

for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i

So:

fact[0] = 1
fact[1] = 1
fact[2] = 2
fact[3] = 6
fact[4] = 24

Convert k to zero-based:

k -= 1

Then process each position:

for remaining in range(n, 0, -1):

If there are remaining digits left, each candidate digit controls:

fact[remaining - 1]

permutations.

So:

index = k // block_size

chooses the correct digit.

We append and remove that digit:

ans.append(digits.pop(index))

Then shrink k to the offset inside the selected block:

k %= block_size

Finally:

return "".join(ans)

Testing

def run_tests():
    s = Solution()

    assert s.getPermutation(3, 3) == "213"
    assert s.getPermutation(4, 9) == "2314"
    assert s.getPermutation(3, 1) == "123"
    assert s.getPermutation(1, 1) == "1"
    assert s.getPermutation(3, 6) == "321"
    assert s.getPermutation(4, 24) == "4321"

    print("all tests passed")

run_tests()