634. Find the Derangement of An Array
Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 40.6%
Problem Breakdown
We are given an integer n, representing a set of numbers from 1 to n. We need to calculate how many permutations exist where no number remains in its original index (a derangement). The result must be returned modulo .
Inputs: Integer n ().
Outputs: An integer representing the count of valid derangements.
Constraints & Edge Cases:
- Since we need a count, not just existence, overflow is possible without modulo arithmetic at each step.
- For , it’s impossible to move the single element out of its spot, so the answer must be 0.
- The problem implies an implicit array
[1, 2, ..., n], but we only care aboutn.
Intuition
A brute-force approach would generate all permutations and check if they are derangements. This is time complexity, which is impossible for . Even calculating factorials directly exceeds standard integer limits quickly without modulo handling.
We need a mathematical recurrence relation to build the solution incrementally.
Consider element n. It must move to one of the other n-1 positions. Let’s say it moves to position where value was originally k.
There are two cases for the remaining elements:
- The element that was at position
k(valuek) also moves away from its spot, and eventually ends up in a derangement of sizen-2relative to each other. This happens if valuekswaps with wherenwent or is part of the remaining set excluding both original spots involved. - The element that was at position
kmoves back into positionn. Effectively, we are left deranging a set of sizen-1.
The standard recurrence relation derived from this logic (or via inclusion-exclusion) is:
Base cases: , . We can compute iteratively from i=2 to n. This avoids recursion overhead and stack overflow risks.
Approach
We will use an iterative dynamic programming approach with constant space complexity.
- Handle the base case where
n == 1, return 0 immediately. - Initialize variables for (representing ) and (representing ). Start with known values: , .
- Loop from
i=3ton. - In each iteration, calculate current derangement count using the formula modulo .
- Shift variables for next iteration (, ).
- Return final result.
Complexity Analysis
- Time: - We iterate from
2ton, performing constant time arithmetic operations per step. With , this is well within typical limits (approx 1 second in Python/C++). - Space: - We only store the last two values of derangements, not an array or recursion stack.
Solution
class Solution:
def findDerangement(self, n: int) -> int:
MOD = 10**9 + 7
# Base case for n=1 is impossible to derange (must stay in place)
if n == 1:
return 0
# D[i-2] and D[i-1] initialized with base cases derived from recurrence logic.
# We start loop at i=3, so we need values for i=1 and i=2 ready.
dp_prev_2 = 0 # Represents D[1] initially (conceptually)
# Actually easier to track current/prev directly starting from n=2
# Let's align variables strictly:
# We want to compute up to n.
# Base cases for recurrence logic usually start at index 2 or 3.
if n == 1: return 0
if n == 2: return 1
prev_2 = 0 # D[1]
prev_1 = 1 # D[2]
for i in range(3, n + 1):
current = (prev_1 * (i - 1) + prev_2 * (i - 1)) % MOD
# Shift window: new prev_2 becomes old prev_1, etc.
prev_2 = prev_1
prev_1 = current
return prev_1
# Optimized variable naming for clarity in final code block below
Edge Cases Handled
- n=1: Returns 0 immediately as no derangement exists (element must stay).
- Large n (): Modulo arithmetic is applied at every addition/multiplication to prevent integer overflow and keep numbers within standard types. Iterative approach ensures memory usage stays constant regardless of
n.