LeetCode 634: Find the Derangement of An Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 634: Find the Derangement of An Array?

In LeetCode 634: Find the Derangement of An Array, you’re given an integer n, representing an array of numbers from 1 to n, and your task is to count how many distinct permutations exist where no element appears in its original position—i.e., no i maps to i. This is a derangement, and the result must be returned modulo 10⁹ + 7 (1,000,000,007). For example, with n = 3, valid derangements are [2, 3, 1] and [3, 1, 2] (2 total), but [1, 2, 3] doesn’t count because 1 is in position 1. This problem tests your ability to handle combinatorial counting with modulo constraints.

Problem Statement

• Input:
• n: An integer (1 ≤ n ≤ 10⁶).
• Output: An integer—number of derangements of an array of size n, modulo 10⁹ + 7.
• Rules:
• Array contains numbers 1 to n exactly once.
• No element stays in its original position (nums[i] ≠ i+1).
• Return result % (10⁹ + 7).

Constraints

• 1 ≤ n ≤ 10⁶.

Examples

• Input: n = 3
• Output: 2 (Derangements: [2, 3, 1], [3, 1, 2])
• Input: n = 2
• Output: 1 (Derangement: [2, 1])
• Input: n = 1
• Output: 0 (No derangement possible)

These examples set the scene—let’s solve it!

Understanding the Problem: Counting Derangements

To solve LeetCode 634: Find the Derangement of An Array in Python, we need to count permutations of numbers 1 to n where no element is in its original position, handling large results with modulo 10⁹ + 7. A brute-force approach—generating all n! permutations and checking each—is O(n!), infeasible for n up to 10⁶. Instead, we’ll use dynamic programming or recursion to compute this efficiently, leveraging the mathematical pattern of derangements (denoted !n or D(n)). We’ll explore:

• Best Solution (DP with Modulo Arithmetic): O(n) time, O(1) space—fast and space-efficient.
• Alternative Solution (Recursive with Memoization): O(n) time, O(n) space—intuitive but uses more memory.

Let’s start with the DP solution, breaking it down for beginners.

Best Solution: Dynamic Programming with Modulo Arithmetic

Why This Is the Best Solution

The dynamic programming approach with modulo arithmetic is the top choice for LeetCode 634 because it’s highly efficient—O(n) time with O(1) space—and uses a recurrence relation optimized for space by tracking only the last two values. It fits constraints (n ≤ 10⁶) perfectly and handles modulo operations seamlessly. It’s like counting surprises step-by-step, refining as you go!

How It Works

Think of this as a derangement builder:

• Step 1: Define Derangement (D(n)):
• D(n): Number of derangements for n elements.
• Step 2: Base Cases:
• D(1) = 0 (no derangement: [1]).
• D(2) = 1 ([2, 1]).
• Step 3: Recurrence Relation:
• For n ≥ 3: D(n) = (n - 1) * [D(n - 1) + D(n - 2)].
• Why? Place n in any of n-1 positions, consider subcases:
• n swaps with some k: n-1 derangements (D(n-2)).
• n goes elsewhere: n-1 choices, n-1 derangements (D(n-1)).
• Step 4: Optimize Space:
• Use two variables to track D(n-1) and D(n-2).
• Step 5: Apply Modulo:
• Compute % (10⁹ + 7) at each step.
• Step 6: Return Result:
• Return D(n).

It’s like a counting ladder—climb with math!

Step-by-Step Example

Example: n = 4

• Step 1: Init:
• MOD = 10⁹ + 7.
• prev2 = 0 (D(1)), prev1 = 1 (D(2)).
• Step 2: Compute:
• n = 3:
• D(3) = (3-1) (D(2) + D(1)) = 2 (1 + 0) = 2.
• prev2 = 1, prev1 = 2.
• n = 4:
• D(4) = (4-1) (D(3) + D(2)) = 3 (2 + 1) = 9.
• prev2 = 2, prev1 = 9.
• Step 3: Return D(4) = 9.
• Output: 9 (Derangements: [2,1,4,3], [2,3,4,1], [2,4,1,3], [3,1,4,2], [3,4,1,2], [3,4,2,1], [4,1,2,3], [4,3,1,2], [4,3,2,1]).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def findDerangement(self, n: int) -> int:
        # Step 1: Define modulo constant
        MOD = 10**9 + 7

        # Step 2: Handle base cases
        if n == 1:
            return 0
        if n == 2:
            return 1

        # Step 3: Initialize for DP
        prev2 = 0  # D(1)
        prev1 = 1  # D(2)

        # Step 4: Compute D(n) iteratively
        for i in range(3, n + 1):
            curr = (i - 1) * (prev1 + prev2) % MOD
            prev2, prev1 = prev1, curr

        # Step 5: Return result
        return prev1

• Line 4: Set MOD = 10⁹ + 7.
• Lines 7-10: Base cases: D(1) = 0, D(2) = 1.
• Lines 13-14: Init prev values for DP.
• Lines 17-19: Iterate:
• Use recurrence, update with modulo, shift variables.
• Time Complexity: O(n)—linear iteration.
• Space Complexity: O(1)—two variables.

This is like a derangement counter—fast and lean!

Alternative Solution: Recursive with Memoization

Why an Alternative Approach?

The recursive with memoization approach computes D(n) top-down—O(n) time, O(n) space. It’s more intuitive, breaking the problem into subproblems with a clear recurrence, but uses more memory due to the memo table. It’s like exploring all shuffle possibilities and caching them!

How It Works

Picture this as a shuffle explorer:

• Step 1: Define D(n) recursively:
• D(n) = (n-1) * [D(n-1) + D(n-2)].
• Step 2: Base cases:
• D(1) = 0, D(2) = 1.
• Step 3: Memoize results.
• Step 4: Apply modulo at each step.
• Step 5: Return D(n).

It’s like a recursive shuffler—clear but bulkier!

Step-by-Step Example

Example: n = 3

• Step 1: Call D(3):
• D(3) = (3-1) * (D(2) + D(1)).
• Step 2:
• D(2) = 1 (base).
• D(1) = 0 (base).
• Step 3: D(3) = 2 * (1 + 0) = 2.
• Output: 2.

Code for Recursive Approach

Copy codeclass Solution:
    def findDerangement(self, n: int) -> int:
        MOD = 10**9 + 7
        memo = {}

        def D(n):
            if n == 1:
                return 0
            if n == 2:
                return 1
            if n in memo:
                return memo[n]

            result = (n - 1) * (D(n - 1) + D(n - 2)) % MOD
            memo[n] = result
            return result

        return D(n)

• Lines 4-5: Init memo and MOD.
• Lines 7-16: Recursive function:
• Base cases, memo check, compute recurrence.
• Time Complexity: O(n)—n states memoized.
• Space Complexity: O(n)—memo table.

It’s a memoized counter—intuitive but heavier!

Comparing the Two Solutions

• DP (Best):
• Pros: O(n) time, O(1) space, fast and minimal.
• Cons: Less intuitive recurrence.
• Recursive (Alternative):
• Pros: O(n) time, O(n) space, clear recursion.
• Cons: More memory.

DP wins for efficiency.

Additional Examples and Edge Cases

• Input: n = 4
• Output: 9.
• Input: n = 5
• Output: 44.

Both handle these well.

Complexity Breakdown

• DP: Time O(n), Space O(1).
• Recursive: Time O(n), Space O(n).

DP is optimal.

Key Takeaways

• DP: Space-saving math—smart!
• Recursive: Memoized clarity—clear!
• Counting: Derangements are fun.
• Python Tip: Loops rock—see Python Basics.

Final Thoughts: Count Those Derangements

LeetCode 634: Find the Derangement of An Array in Python is a fascinating combinatorics challenge. DP with modulo offers speed and minimalism, while recursive memoization provides clarity. Want more? Try LeetCode 377: Combination Sum IV or LeetCode 96: Unique Binary Search Trees. Ready to shuffle? Head to Solve LeetCode 634 on LeetCode and count those derangements today!