# LeetCode 60: Permutation Sequence

## Problem Restatement

We are given two integers, `n` and `k`.

The set is:

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

This set has `n!` unique permutations.

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

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `n` and `k` |
| Output | The `k`th permutation sequence as a string |
| Digits used | `1` through `n` |
| Order | Lexicographic permutation order |
| Indexing | `k` is 1-indexed |

Function shape:

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

## Examples

For:

```python
n = 3
k = 3
```

The permutations in order are:

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

The 3rd permutation is:

```python
"213"
```

For:

```python
n = 4
k = 9
```

The answer is:

```python
"2314"
```

For:

```python
n = 3
k = 1
```

The answer is:

```python
"123"
```

## First Thought: Generate All Permutations

A direct solution is:

1. Generate all permutations of `[1, 2, ..., n]`.
2. Sort them.
3. Return the `k`th 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:

```python
[1, 2, 3, 4]
```

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

```python
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:

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

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

```python
k -= 1
```

Now:

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

This makes the block calculation cleaner.

## Walkthrough

Use:

```python
n = 4
k = 9
```

First convert:

```python
k = 8
```

Available digits:

```python
[1, 2, 3, 4]
```

For the first position, each starting digit has:

```python
3! = 6
```

permutations.

Compute:

```python
index = 8 // 6 = 1
```

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

Result so far:

```python
"2"
```

Update:

```python
k = 8 % 6 = 2
```

Remaining digits:

```python
[1, 3, 4]
```

For the second position, each digit controls:

```python
2! = 2
```

permutations.

Compute:

```python
index = 2 // 2 = 1
```

Choose digit at index `1`, which is `3`.

Result:

```python
"23"
```

Update:

```python
k = 2 % 2 = 0
```

Remaining digits:

```python
[1, 4]
```

For the third position, each digit controls:

```python
1! = 1
```

Compute:

```python
index = 0 // 1 = 0
```

Choose `1`.

Result:

```python
"231"
```

Remaining digit:

```python
[4]
```

Final result:

```python
"2314"
```

## Algorithm

Create a list of available digits:

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

Precompute factorials:

```python
fact[i] = i!
```

Convert `k` to zero-based:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Removing from the middle of a Python list costs `O(n)` and happens `n` times |
| Space | `O(n)` | We store digits, factorials, and the answer |

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

## Implementation

```python
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:

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

For `n = 4`, this gives:

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

Then we precompute factorials:

```python
fact = [1] * (n + 1)

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

So:

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

Convert `k` to zero-based:

```python
k -= 1
```

Then process each position:

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

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

```python
fact[remaining - 1]
```

permutations.

So:

```python
index = k // block_size
```

chooses the correct digit.

We append and remove that digit:

```python
ans.append(digits.pop(index))
```

Then shrink `k` to the offset inside the selected block:

```python
k %= block_size
```

Finally:

```python
return "".join(ans)
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `n = 3, k = 3` | Official example |
| `n = 4, k = 9` | Official example with multiple block skips |
| `n = 3, k = 1` | First permutation |
| `n = 1, k = 1` | Smallest input |
| `n = 3, k = 6` | Last permutation for `n = 3` |
| `n = 4, k = 24` | Last permutation for `n = 4` |