Watch 6 video solutions for Find the Derangement of An Array, a medium level problem involving Math, Dynamic Programming. This walkthrough by XIAOLONG has 637 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |