In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.
You are given an integer n. There is originally an array consisting of n integers from 1 to n in ascending order, return the number of derangements it can generate. Since the answer may be huge, return it modulo 109 + 7.
Example 1:
Input: n = 3 Output: 2 Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
Example 2:
Input: n = 2 Output: 1
Constraints:
1 <= n <= 106Problem Overview: You are given an integer n representing the size of an array containing numbers 1..n. The task is to count how many permutations exist where no element appears in its original position. This is called a derangement. The result must be returned modulo 1e9 + 7.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
Derangements follow a classic recurrence relation from math and dynamic programming. If D(n) represents the number of derangements for size n, the recurrence is D(n) = (n - 1) * (D(n - 1) + D(n - 2)). The reasoning: choose a position for element 1 among n-1 spots. If the swapped element goes to position 1, the remaining array behaves like D(n-2). Otherwise, it behaves like D(n-1). Build a DP array where each entry stores the derangement count for that size. Start with base cases D(1) = 0 and D(2) = 1, then iterate from 3 to n applying the recurrence and taking modulo 1e9+7. This approach is straightforward and mirrors the mathematical definition directly. Time complexity is O(n) because you compute each state once, and space complexity is O(n) for the DP table.
Approach 2: Dynamic Programming (Space Optimization) (O(n) time, O(1) space)
The recurrence only depends on the previous two values: D(n-1) and D(n-2). Storing the entire DP table is unnecessary. Instead, keep two variables representing these states and update them while iterating from 3 to n. Each iteration computes the next value using the same recurrence and shifts the variables forward. This reduces auxiliary memory to constant space while preserving the same O(n) time complexity. The modulo operation still applies during each multiplication to prevent overflow.
This version is typically preferred in production or competitive programming because it uses minimal memory and still expresses the mathematical recurrence clearly. The logic remains identical to the full DP version, but with two rolling variables instead of an array.
Recommended for interviews: Start by explaining the recurrence relation for derangements. That shows understanding of the combinatorial structure of the problem. Implement the O(n) dynamic programming solution first for clarity, then mention the constant-space optimization. Interviewers expect the recurrence-based DP because brute force permutation generation would take O(n!) time and is infeasible even for moderate n.
We define f[i] as the number of derangement of an array of length i. Initially, f[0] = 1, f[1] = 0. The answer is f[n].
For an array of length i, we consider where to place the number 1. Suppose it is placed in the j-th position, where there are i-1 choices. Then, the number j has two choices:
i - 2 positions have f[i - 2] derangements, so there are a total of (i - 1) times f[i - 2] derangements;i - 1, so there are a total of (i - 1) times f[i - 1] derangements.In summary, we have the following state transition equation:
$
f[i] = (i - 1) times (f[i - 1] + f[i - 2])
The final answer is f[n]. Note the modulo operation in the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.
We notice that the state transition equation only relates to f[i - 1] and f[i - 2]. Therefore, we can use two variables a and b to represent f[i - 1] and f[i - 2] respectively, thereby reducing the space complexity to O(1).
| Approach | Complexity |
|---|---|
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (DP array) | O(n) | O(n) | Best for understanding the recurrence and debugging intermediate values |
| Dynamic Programming (Space Optimized) | O(n) | O(1) | Preferred in interviews and competitive programming when memory usage matters |
[DP]634.Find the Derangement of An Array • XIAOLONG • 637 views views
Watch 5 more video solutions →Practice Find the Derangement of An Array with our built-in code editor and test cases.
Practice on FleetCode