Find the Derangement of An Array - Solution & Explanation
Problem Statement
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 <= 106
Approach Overview
Problem 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.
Approach 1: Dynamic Programming
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:
- Placed in the first position, then the remaining
i - 2positions havef[i - 2]derangements, so there are a total of(i - 1) times f[i - 2]derangements; - Not placed in the first position, which is equivalent to the derangement of an array of length
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)$.
Approach 2: Dynamic Programming (Space Optimization)
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).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| 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 |
Video Solution
[DP]634.Find the Derangement of An Array • XIAOLONG • 642 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Find the Derangement of An Array easy or hard?
Find the Derangement of An Array Python/Java solution
How to solve Find the Derangement of An Array in O(n)?
What is the best approach for Find the Derangement of An Array?
Is Find the Derangement of An Array asked at Google/Amazon/Meta?
What data structure is used in Find the Derangement of An Array?
What is the time complexity of Find the Derangement of An Array?
Ready to solve this problem?
Practice Find the Derangement of An Array with our built-in code editor and test cases.
Practice on FleetCode