# LeetCode 634: Find the Derangement of An Array

## Problem Restatement

We are given an integer `n`.

We need to count how many permutations of the numbers:

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

have no fixed positions.

A fixed position means:

```python
perm[i] == i
```

for some index.

A permutation with no fixed positions is called a derangement.

Because the answer can be very large, return it modulo:

```python
10**9 + 7
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of derangements of size `n` |
| Modulo | `10^9 + 7` |

Example function shape:

```python
def findDerangement(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 3
```

The permutations of `[1, 2, 3]` are:

| Permutation | Fixed Position? |
|---|---|
| `[1, 2, 3]` | yes |
| `[1, 3, 2]` | yes |
| `[2, 1, 3]` | yes |
| `[2, 3, 1]` | no |
| `[3, 1, 2]` | no |
| `[3, 2, 1]` | yes |

Only two permutations are valid:

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

So the answer is:

```python
2
```

Example 2:

```python
n = 2
```

Possible permutations:

| Permutation | Valid? |
|---|---|
| `[1, 2]` | no |
| `[2, 1]` | yes |

So the answer is:

```python
1
```

## First Thought: Generate All Permutations

We could generate every permutation and count the ones with no fixed positions.

But there are:

```python
n!
```

permutations.

This becomes impossible even for moderate values of `n`.

We need a mathematical recurrence.

## Key Insight

Let:

```python
dp[n]
```

mean:

```text
the number of derangements of size n
```

We want to derive a recurrence relation.

Focus on the position of number `1`.

Since this is a derangement, `1` cannot stay at position `1`.

Suppose `1` moves to position `k`.

Now consider the number originally at position `k`.

There are two possibilities.

## Case 1: Swap

Suppose the number at position `k` moves to position `1`.

Then:

```text
1 and k swap positions
```

After fixing this pair, the remaining:

```python
n - 2
```

elements must form a derangement.

So this case contributes:

```python
dp[n - 2]
```

ways.

## Case 2: No Swap

Suppose the number at position `k` does not move to position `1`.

Then we can think of the remaining problem as a derangement of:

```python
n - 1
```

elements.

So this case contributes:

```python
dp[n - 1]
```

ways.

## Building the Recurrence

There are:

```python
n - 1
```

possible choices for where `1` goes.

For each choice, the total number of valid arrangements is:

```python
dp[n - 1] + dp[n - 2]
```

Therefore:

```python
dp[n] = (n - 1) * (dp[n - 1] + dp[n - 2])
```

This is the classic derangement recurrence.

## Base Cases

For:

```python
n = 1
```

there is no valid derangement:

```python
dp[1] = 0
```

For:

```python
n = 2
```

there is exactly one derangement:

```python
[2, 1]
```

So:

```python
dp[2] = 1
```

## Algorithm

1. Handle base cases.
2. Build the DP recurrence from `3` up to `n`.
3. Apply modulo after every operation.
4. Return `dp[n]`.

## Implementation

```python
class Solution:
    def findDerangement(self, n: int) -> int:
        MOD = 10**9 + 7

        if n == 1:
            return 0

        if n == 2:
            return 1

        dp1 = 0
        dp2 = 1

        for size in range(3, n + 1):
            current = (size - 1) * (dp1 + dp2)
            current %= MOD

            dp1 = dp2
            dp2 = current

        return dp2
```

## Code Explanation

We use rolling variables instead of a full array.

```python
dp1 = 0
dp2 = 1
```

These represent:

| Variable | Meaning |
|---|---|
| `dp1` | `dp[n - 2]` |
| `dp2` | `dp[n - 1]` |

For each new size:

```python
current = (size - 1) * (dp1 + dp2)
```

This directly implements:

```python
dp[n] = (n - 1) * (dp[n - 1] + dp[n - 2])
```

Then we shift the rolling variables forward:

```python
dp1 = dp2
dp2 = current
```

Finally:

```python
return dp2
```

returns the answer for size `n`.

## Correctness

We prove that the recurrence:

```python
dp[n] = (n - 1) * (dp[n - 1] + dp[n - 2])
```

correctly counts all derangements of size `n`.

Consider any derangement of:

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

The number `1` cannot stay in position `1`, so it must move to one of the other:

```python
n - 1
```

positions.

Suppose `1` moves to position `k`.

Now consider the element originally at position `k`.

If that element moves to position `1`, then `1` and `k` form a swap. The remaining `n - 2` elements must form a derangement. This gives:

```python
dp[n - 2]
```

possibilities.

Otherwise, the element from position `k` does not move to position `1`. In this case, the remaining structure corresponds to a derangement of size:

```python
n - 1
```

This gives:

```python
dp[n - 1]
```

possibilities.

Since there are:

```python
n - 1
```

choices for the destination of `1`, the total number of derangements is:

```python
(n - 1) * (dp[n - 1] + dp[n - 2])
```

Therefore the recurrence is correct.

The base cases are also correct:

| `n` | Value | Reason |
|---|---:|---|
| `1` | `0` | The only permutation fixes the element |
| `2` | `1` | Only `[2,1]` is valid |

Thus the algorithm computes the correct number of derangements.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One DP transition per size |
| Space | `O(1)` | Only rolling variables are stored |

## Alternative Solution: Full DP Table

We can also store every DP value.

```python
class Solution:
    def findDerangement(self, n: int) -> int:
        MOD = 10**9 + 7

        if n == 1:
            return 0

        dp = [0] * (n + 1)

        dp[1] = 0
        dp[2] = 1

        for i in range(3, n + 1):
            dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
            dp[i] %= MOD

        return dp[n]
```

This is simpler conceptually but uses more memory.

| Metric | Value |
|---|---:|
| Time | `O(n)` |
| Space | `O(n)` |

## Mathematical Formula

The number of derangements is often written as:

```python
!n
```

There is also a closed-form formula:

```text
!n = n! * (1 - 1/1! + 1/2! - 1/3! + ...)
```

More precisely:

```text
!n = nearest integer to n! / e
```

But the recurrence solution is much easier and safer for programming problems.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findDerangement(1) == 0
    assert s.findDerangement(2) == 1
    assert s.findDerangement(3) == 2
    assert s.findDerangement(4) == 9
    assert s.findDerangement(5) == 44
    assert s.findDerangement(6) == 265

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | Smallest input |
| `2` | First non-zero answer |
| `3` | Official example |
| `4` | Standard recurrence check |
| `5` | Larger combinatorial count |
| `6` | Confirms recurrence growth |