LeetCode 634 - Find the Derangement of An Array

The problem asks us to count how many permutations of the numbers 1 through n are valid derangements. A derangement is a permutation where no element remains in its original position. For example, when n = 3, the original array is [1, 2, 3].

leetcodemediummathdynamic-programmingcombinatorics

LeetCode Problem 634

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Combinatorics

Solution

Problem Understanding

The problem asks us to count how many permutations of the numbers 1 through n are valid derangements. A derangement is a permutation where no element remains in its original position.

For example, when n = 3, the original array is [1, 2, 3]. A permutation like [2, 3, 1] is valid because:

  • 1 is not at index 0
  • 2 is not at index 1
  • 3 is not at index 2

However, [1, 3, 2] is not a derangement because 1 remains in its original position.

The input consists of a single integer n, and the output should be the total number of valid derangements modulo 10^9 + 7.

The constraints are important:

  • 1 <= n <= 10^6

A value of 10^6 is extremely large for combinatorial generation. This immediately tells us that generating permutations explicitly is impossible. Since the number of permutations is n!, even small values become enormous very quickly.

This means we need a mathematical or dynamic programming approach with linear or near linear complexity.

Several edge cases are especially important:

  • n = 1, there is no way to rearrange one element without keeping it in place, so the answer is 0
  • n = 2, only [2,1] works, so the answer is 1
  • Very large n, where overflow becomes a concern, meaning modulo arithmetic must be applied during computation
  • Recursive solutions without optimization may cause stack overflow for large n

Approaches

Brute Force Approach

The brute force solution would generate every permutation of the array [1,2,...,n] and check whether every element differs from its original position.

For each permutation:

  1. Compare every position with the original array
  2. If no positions match, increment the answer

This approach is correct because it exhaustively checks every possible arrangement.

However, the number of permutations is n!, which grows extremely quickly:

  • 10! = 3,628,800
  • 15! already exceeds one trillion

Since n can be as large as 10^6, brute force is completely infeasible.

Optimal Dynamic Programming Approach

The key observation is that derangements follow a well known recurrence relation.

Let D(n) represent the number of derangements for n elements.

We derive the recurrence as follows:

Take element 1.

Since it cannot stay in position 1, it must go into one of the other n - 1 positions.

Suppose it goes into position k.

Now consider the element originally at position k.

There are two possibilities:

  1. That element moves into position 1
  2. That element does not move into position 1

These two cases lead directly to the recurrence:

$$D(n) = (n - 1) \times (D(n - 1) + D(n - 2))$$

with base cases:

$$D(1) = 0$$

$$D(2) = 1$$

This recurrence allows us to compute the answer iteratively in linear time.

$D(n)=(n-1)(D(n-1)+D(n-2))$

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n!) Generates every permutation and checks validity
Optimal Dynamic Programming O(n) O(1) Uses the derangement recurrence relation

Algorithm Walkthrough

  1. Define the modulo constant MOD = 10^9 + 7.

Since the result grows extremely quickly, modulo arithmetic must be applied during every computation step to avoid overflow. 2. Handle small base cases.

The recurrence depends on previous values, so we must initialize:

  • D(1) = 0
  • D(2) = 1
  1. Store the previous two derangement counts.

Instead of maintaining an entire DP array, we only need the two most recent values:

  • prev2 = D(n-2)
  • prev1 = D(n-1)

This reduces space complexity from O(n) to O(1). 4. Iterate from 3 to n.

For each value:

$$D(i) = (i - 1) \times (D(i-1) + D(i-2))$$

Apply modulo arithmetic immediately after computing the value. 5. Shift the variables forward.

After computing the current derangement count:

  • prev2 = prev1
  • prev1 = current
  1. Return the final computed value.

After the loop completes, prev1 contains D(n).

Why it works

The recurrence works because each derangement can be categorized based on where the first element moves.

If element 1 moves to position k, then either:

  • the element at k swaps back to position 1, producing a subproblem of size n-2
  • or it moves elsewhere, producing a subproblem of size n-1

There are n-1 choices for k, so multiplying by n-1 accounts for all valid possibilities exactly once.

Python Solution

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

        if n == 1:
            return 0

        if n == 2:
            return 1

        prev2 = 0  # D(1)
        prev1 = 1  # D(2)

        for i in range(3, n + 1):
            current = (i - 1) * (prev1 + prev2) % MOD
            prev2 = prev1
            prev1 = current

        return prev1

The implementation starts by defining the modulo constant and handling the smallest edge cases directly.

The variables prev2 and prev1 represent the two previously computed derangement values required by the recurrence relation.

The loop computes the derangement count iteratively from 3 up to n. At each step, the recurrence relation is applied and modulo arithmetic ensures the values remain within bounds.

Because only the previous two states are required, the implementation avoids storing a full DP array and achieves constant extra memory usage.

Go Solution

func findDerangement(n int) int {
    const MOD int = 1000000007

    if n == 1 {
        return 0
    }

    if n == 2 {
        return 1
    }

    prev2 := 0 // D(1)
    prev1 := 1 // D(2)

    for i := 3; i <= n; i++ {
        current := ((i - 1) * (prev1 + prev2)) % MOD
        prev2 = prev1
        prev1 = current
    }

    return prev1
}

The Go implementation follows the same iterative dynamic programming logic as the Python version.

One important difference is explicit integer handling. Since Go integers can overflow depending on platform size, modulo arithmetic is applied immediately during computation.

The implementation also avoids recursion, which is important because recursive depth for n = 10^6 would be unsafe.

Worked Examples

Example 1

Input:

n = 3

Initial state:

Variable Value
prev2 0
prev1 1

Iteration for i = 3:

$$D(3) = (3-1) \times (D(2)+D(1))$$

$$= 2 \times (1+0)$$

$$= 2$$

State update:

Variable Value
current 2
prev2 1
prev1 2

Final answer:

2

The two derangements are:

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

Example 2

Input:

n = 2

The algorithm immediately returns the base case:

$$D(2) = 1$$

Final answer:

1

The only valid derangement is:

[2,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) One loop from 3 to n
Space O(1) Only a few variables are stored

The recurrence requires only the previous two values, so there is no need for an array or recursion stack. Each iteration performs constant work, resulting in linear runtime overall.

Test Cases

solution = Solution()

assert solution.findDerangement(1) == 0  # smallest input
assert solution.findDerangement(2) == 1  # first valid derangement
assert solution.findDerangement(3) == 2  # example case
assert solution.findDerangement(4) == 9  # standard recurrence expansion
assert solution.findDerangement(5) == 44  # larger recurrence value
assert solution.findDerangement(6) == 265  # verifies continued recurrence correctness
assert solution.findDerangement(7) == 1854  # medium sized test
assert solution.findDerangement(8) == 14833  # larger DP progression
assert solution.findDerangement(9) == 133496  # checks correctness for bigger values
assert solution.findDerangement(10) == 1334961  # verifies recurrence scaling

# stress test for large input
result = solution.findDerangement(10**6)
assert isinstance(result, int)  # ensures algorithm handles maximum constraints efficiently

Test Case Summary

Test Why
n = 1 Verifies smallest edge case
n = 2 Verifies first nonzero derangement
n = 3 Matches problem example
n = 4 Confirms recurrence correctness
n = 5 Tests multiple iterations
n = 6 Verifies continued DP growth
n = 7 Medium sized correctness check
n = 8 Larger recurrence validation
n = 9 Confirms scaling behavior
n = 10 Checks larger combinatorial count
n = 10^6 Stress test for performance and modulo handling

Edge Cases

One important edge case is n = 1. With only one element, there is no possible rearrangement where the element changes position. A naive recurrence implementation might accidentally return 1 if base cases are not handled carefully. The implementation explicitly returns 0 for this case.

Another important edge case is n = 2. This is the smallest nontrivial derangement scenario. The only valid permutation is [2,1]. Since the recurrence depends on earlier values, incorrectly initializing the base cases would cause all later computations to become incorrect. The implementation sets D(2) = 1 explicitly.

A third critical edge case is very large input values such as n = 10^6. Recursive implementations may exceed recursion depth limits or consume excessive memory. Similarly, storing a full DP table is unnecessary overhead. The implementation uses an iterative approach with only two variables, ensuring both memory efficiency and scalability.

Another subtle issue is integer overflow. Derangement counts grow extremely quickly, far beyond standard integer limits. The implementation applies modulo arithmetic during every iteration so intermediate values remain manageable and correct according to the problem requirements.