Count Derangements (Permutation such that no element appears in its original position) [IMPORTANT]

Problem Statement

A derangement is a permutation of elements where no element appears in its original position. Given a number n, count the total number of derangements of a set of n elements. Since the answer can be large, return it modulo 10^9 + 7.

Example:

• Input: n = 3

• Output: 2

• Explanation: For set {1, 2, 3}, the derangements are {2, 3, 1} and {3, 1, 2}. In both, no element is at its original index.

• Input: n = 4

• Output: 9

Noob-Friendly Explanation

Imagine you have 3 friends and 3 gift boxes labeled with their names. You want to distribute the gifts such that nobody gets the box with their own name on it. How many ways can you do this?

For 3 friends (A, B, C): the valid distributions are (B gets C's, C gets A's, A gets B's) and (C gets B's, A gets C's, B gets A's). That's 2 ways. This count is called a "derangement."

Approach 1: Brute Force (Generate All Permutations)

Intuition

Generate all permutations of the array [1, 2, ..., n] and count those where no element is at its original position (i.e., perm[i] != i for all i).

Algorithm

1. Generate all n! permutations.
2. For each permutation, check if no element is at its original position.
3. Count valid permutations.

class Solution {
    int count = 0;

    public int countDerangements(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = i;
        boolean[] used = new boolean[n];
        int[] perm = new int[n];
        generatePerms(arr, perm, used, 0, n);
        return count;
    }

    private void generatePerms(int[] arr, int[] perm, boolean[] used, int pos, int n) {
        if (pos == n) {
            // Check if it's a derangement
            boolean isDerangement = true;
            for (int i = 0; i < n; i++) {
                if (perm[i] == i) {
                    isDerangement = false;
                    break;
                }
            }
            if (isDerangement) count++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                perm[pos] = arr[i];
                generatePerms(arr, perm, used, pos + 1, n);
                used[i] = false;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(n!) - We generate all permutations.
• Space Complexity: O(n) - For the recursion stack and temporary arrays.

Approach 2: Optimal (Dynamic Programming)

Intuition

The number of derangements follows a recurrence relation: D(n) = (n - 1) * (D(n - 1) + D(n - 2)). The logic: element 1 can go to any of the other n-1 positions (say position k). Now, element k has two options: go to position 1 (which reduces to D(n-2)) or not go to position 1 (which reduces to D(n-1)).

Algorithm

1. Base cases: D(1) = 0 (one element must stay in place), D(2) = 1 (swap the two).
2. For i from 3 to n: D(i) = (i - 1) * (D(i - 1) + D(i - 2)).
3. Use modular arithmetic to handle large numbers.

class Solution {
    public int countDerangements(int n) {
        long MOD = 1000000007;

        if (n == 1) return 0;
        if (n == 2) return 1;

        long prev2 = 0; // D(1)
        long prev1 = 1; // D(2)

        for (int i = 3; i <= n; i++) {
            long curr = ((i - 1) % MOD * ((prev1 + prev2) % MOD)) % MOD;
            prev2 = prev1;
            prev1 = curr;
        }

        return (int) prev1;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single loop from 3 to n.
• Space Complexity: O(1) - Only two variables used to track previous values.