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:

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

have no fixed positions.

A fixed position means:

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:

10**9 + 7

Input and Output

Example function shape:

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

Examples

Example 1:

n = 3

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

Only two permutations are valid:

[2, 3, 1]
[3, 1, 2]

So the answer is:

2

Example 2:

n = 2

Possible permutations:

So the answer is:

1

First Thought: Generate All Permutations

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

But there are:

n!

permutations.

This becomes impossible even for moderate values of n.

We need a mathematical recurrence.

Key Insight

Let:

dp[n]

mean:

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:

1 and k swap positions

After fixing this pair, the remaining:

n - 2

elements must form a derangement.

So this case contributes:

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:

n - 1

elements.

So this case contributes:

dp[n - 1]

ways.

Building the Recurrence

There are:

n - 1

possible choices for where 1 goes.

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

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

Therefore:

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

This is the classic derangement recurrence.

Base Cases

For:

n = 1

there is no valid derangement:

dp[1] = 0

For:

n = 2

there is exactly one derangement:

[2, 1]

So:

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

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.

dp1 = 0
dp2 = 1

These represent:

For each new size:

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

This directly implements:

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

Then we shift the rolling variables forward:

dp1 = dp2
dp2 = current

Finally:

return dp2

returns the answer for size n.

Correctness

We prove that the recurrence:

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

correctly counts all derangements of size n.

Consider any derangement of:

[1, 2, ..., n]

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

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:

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:

n - 1

This gives:

dp[n - 1]

possibilities.

Since there are:

n - 1

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

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

Therefore the recurrence is correct.

The base cases are also correct:

Thus the algorithm computes the correct number of derangements.

Complexity

Alternative Solution: Full DP Table

We can also store every DP value.

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.

Mathematical Formula

The number of derangements is often written as:

!n

There is also a closed-form formula:

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

More precisely:

!n = nearest integer to n! / e

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

Testing

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: