Problem Description

A derangement is a special type of permutation where no element appears in its original position. For example, if you have the array [1, 2, 3], a valid derangement would be [2, 3, 1] because:

• 1 is not in position 1 (it's in position 3)
• 2 is not in position 2 (it's in position 1)
• 3 is not in position 3 (it's in position 2)

Given an integer n, you start with an array containing integers from 1 to n in ascending order [1, 2, 3, ..., n]. Your task is to find the total number of possible derangements of this array.

Since the number of derangements can be very large, return the result modulo 10^9 + 7.

For example:

• If n = 3, the original array is [1, 2, 3]
• The possible derangements are: [2, 3, 1] and [3, 1, 2]
• So the answer would be 2

The solution uses dynamic programming with the recurrence relation:

• f[i] = (i - 1) × (f[i - 1] + f[i - 2])

This formula works because when placing element 1 in position j (where j ≠ 1), we have i-1 choices for j. Then element j can either:

• Go to position 1 (leaving i-2 elements to derange): contributes (i-1) × f[i-2] derangements
• Go anywhere except position 1 (equivalent to deranging i-1 elements): contributes (i-1) × f[i-1] derangements

The base cases are f[0] = 1 and f[1] = 0 (no valid derangement for a single element).

Intuition

Let's think about this step by step. When we have an array of size n, we need to place each number in a position that's not its original position.

Start by considering where to place the first element (number 1). It can't go in position 1, so we have n-1 choices for where to place it. Let's say we place it in position k.

Now here's the key insight: what happens to element k? We have two scenarios:

Scenario 1: Element k goes to position 1 If element k takes position 1, we've essentially "paired up" elements 1 and k - they've swapped places. Now we're left with n-2 elements that still need to be deranged among themselves. This gives us f[n-2] ways.

Scenario 2: Element k doesn't go to position 1 If element k doesn't go to position 1, think about what this means. We can mentally "relabel" the problem: imagine element k is now labeled as "1" (since it can't go back to its original position k, just like how 1 couldn't go to position 1). We now have a derangement problem of size n-1. This gives us f[n-1] ways.

Since we had n-1 choices for where to place element 1 initially, and for each choice we get f[n-1] + f[n-2] derangements, the total is:

f[n] = (n-1) × (f[n-1] + f[n-2])

The base cases make sense too:

• f[0] = 1 (empty arrangement is valid by convention)
• f[1] = 0 (one element can't avoid its own position)
• f[2] = 1 (only one way: swap the two elements)

This recursive relationship allows us to build up the solution from smaller subproblems, which is why dynamic programming works perfectly here.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Solution Approach

We implement the solution using dynamic programming with a bottom-up approach. Here's how the algorithm works:

Data Structure: We use an array f of size n+1 where f[i] stores the number of derangements for an array of length i.

Initialization:

• f[0] = 1 (base case: empty arrangement)
• f[1] = 0 (base case: single element can't avoid its position)

Building the Solution: We iterate from i = 2 to n, computing each value using the recurrence relation:

f[i] = (i - 1) × (f[i - 1] + f[i - 2]) % mod

Let's trace through a small example with n = 4:

• f[0] = 1, f[1] = 0
• f[2] = (2-1) × (0 + 1) = 1
• f[3] = (3-1) × (1 + 0) = 2
• f[4] = (4-1) × (2 + 1) = 9

Implementation Details:

1. We initialize the array as f = [1] + [0] * n, which creates an array with f[0] = 1 and the rest as zeros
2. The loop starts from index 2 since we've already set the base cases
3. At each step, we apply the formula and take modulo 10^9 + 7 to prevent integer overflow
4. The final answer is stored in f[n]

Time Complexity: O(n) - we compute each value once from 2 to n

Space Complexity: O(n) - we store the derangement count for each length from 0 to n

The key pattern here is dynamic programming with tabulation, where we build up the solution from smaller subproblems, storing intermediate results to avoid recomputation.

Example Walkthrough

Let's walk through finding the number of derangements for n = 4 using our dynamic programming approach.

Starting array: [1, 2, 3, 4]

We'll build our solution using the formula: f[i] = (i - 1) × (f[i - 1] + f[i - 2])

Step 1: Initialize base cases

• f[0] = 1 (empty arrangement by convention)
• f[1] = 0 (element 1 can't avoid position 1)

Step 2: Calculate f[2]

• Array of size 2: [1, 2]
• f[2] = (2 - 1) × (f[1] + f[0])
• f[2] = 1 × (0 + 1) = 1
• This represents the single derangement: [2, 1]

Step 3: Calculate f[3]

• Array of size 3: [1, 2, 3]
• f[3] = (3 - 1) × (f[2] + f[1])
• f[3] = 2 × (1 + 0) = 2
• This represents two derangements: [2, 3, 1] and [3, 1, 2]

Step 4: Calculate f[4]

• Array of size 4: [1, 2, 3, 4]
• f[4] = (4 - 1) × (f[3] + f[2])
• f[4] = 3 × (2 + 1) = 9

To understand why f[4] = 9, consider placing element 1:

• If 1 goes to position 2: Element 2 can go to position 1 (swap), leaving 2 elements to derange, OR element 2 avoids position 1, creating a size-3 derangement problem
• If 1 goes to position 3: Similar logic applies with element 3
• If 1 goes to position 4: Similar logic applies with element 4

Each of the 3 choices for placing element 1 leads to (f[3] + f[2]) = 3 derangements, giving us 3 × 3 = 9 total.

Final DP array: [1, 0, 1, 2, 9]

The 9 derangements of [1, 2, 3, 4] are:

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

Answer: 9

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the input parameter. The algorithm iterates through a single loop from 2 to n+1, performing constant-time operations (arithmetic operations and modulo) in each iteration.

The space complexity is O(n), not O(1) as stated in the reference answer. The code creates an array f of size n+1 to store intermediate derangement values. While the problem could be optimized to use only O(1) space by keeping track of just the last two values instead of the entire array, the current implementation uses O(n) space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow Without Proper Modulo Application

The Pitfall: A common mistake is applying the modulo operation incorrectly or too late in the calculation. Consider this incorrect implementation:

# INCORRECT - can cause overflow
dp[i] = ((i - 1) * dp[i - 1] + (i - 1) * dp[i - 2]) % MOD

# Also INCORRECT - overflow can happen before modulo
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD  # if intermediate result exceeds integer limit

Why It Happens: When n gets large, the intermediate calculations can exceed integer limits before the modulo operation is applied. In Python, while integers can grow arbitrarily large, in other languages like Java or C++, this would cause integer overflow.

The Solution: Apply modulo at each arithmetic operation step to keep numbers manageable:

# CORRECT approach for languages with integer limits
dp[i] = ((i - 1) * ((dp[i - 1] + dp[i - 2]) % MOD)) % MOD

2. Space Optimization Opportunity Missed

The Pitfall: Using O(n) space when only O(1) space is needed. Since we only need the previous two values to calculate the current one, maintaining the entire array is unnecessary.

The Solution: Use rolling variables instead of an array:

def findDerangement(self, n: int) -> int:
    MOD = 10**9 + 7
  
    if n == 0: return 1
    if n == 1: return 0
  
    # Only track the last two values
    prev2 = 1  # f[i-2], initially f[0]
    prev1 = 0  # f[i-1], initially f[1]
  
    for i in range(2, n + 1):
        current = (i - 1) * (prev1 + prev2) % MOD
        prev2 = prev1
        prev1 = current
  
    return prev1

3. Incorrect Base Cases

The Pitfall: Setting wrong initial values, particularly confusing f[0] = 0 instead of f[0] = 1:

# INCORRECT base case
dp = [0] * (n + 1)  # Wrong: dp[0] should be 1, not 0
dp[1] = 0

Why It Matters: The base case f[0] = 1 represents that there's exactly one way to arrange zero elements (the empty arrangement). This is crucial for the recurrence relation to work correctly.

The Solution: Always verify base cases match the mathematical definition:

• f[0] = 1 (one way to arrange nothing)
• f[1] = 0 (no way to derange a single element)

4. Off-by-One Errors in Array Indexing

The Pitfall: Creating an array of size n instead of n+1, causing index out of bounds:

# INCORRECT - array too small
dp = [1] + [0] * (n - 1)  # Creates array of size n, not n+1

The Solution: Ensure the array has n+1 elements to accommodate indices from 0 to n:

# CORRECT
dp = [1] + [0] * n  # Creates array of size n+1