Domain 2MediumCORE

Find the Derangement of An Array

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 $10^9 + 7$.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math

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 109+710^9 + 7.

Inputs: Integer n (1≤n≤1061 \le n \le 10^6). 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 n=1n=1, 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 about n.

Intuition

A brute-force approach would generate all permutations and check if they are derangements. This is O(n!)O(n!) time complexity, which is impossible for n=106n=10^6. 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:

  1. The element that was at position k (value k) also moves away from its spot, and eventually ends up in a derangement of size n-2 relative to each other. This happens if value k swaps with where n went or is part of the remaining set excluding both original spots involved.
  2. The element that was at position k moves back into position n. Effectively, we are left deranging a set of size n-1.

The standard recurrence relation derived from this logic (or via inclusion-exclusion) is: Dn=(n−1)×(Dn−1+Dn−2)D_n = (n - 1) \times (D_{n-1} + D_{n-2})

Base cases: D0=1D_0 = 1, D1=0D_1 = 0. 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.

  1. Handle the base case where n == 1, return 0 immediately.
  2. Initialize variables for DprevD_{prev} (representing Di−1D_{i-1}) and Dprev_prevD_{prev\_prev} (representing Di−2D_{i-2}). Start with known values: D1=0D_1 = 0, D2=1D_2 = 1.
  3. Loop from i=3 to n.
  4. In each iteration, calculate current derangement count using the formula modulo 109+710^9 + 7.
  5. Shift variables for next iteration (prev_prev←prevprev\_prev \leftarrow prev, prev←currentprev \leftarrow current).
  6. Return final result.

Complexity Analysis

  • Time: O(n)O(n) - We iterate from 2 to n, performing constant time arithmetic operations per step. With N=106N=10^6, this is well within typical limits (approx 1 second in Python/C++).
  • Space: O(1)O(1) - 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 (10610^6): 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.