Find the Derangement of An Array

Find the Derangement of An Array

What is this problem about?

The Find the Derangement of An Array interview question is a combinatorial counting problem. A "derangement" of an array is a permutation where no element appears in its original position. For an array of $n$ elements, you need to find the total number of such permutations. The result can be very large, so it is typically requested modulo $10^9 + 7$.

Why is this asked in interviews?

Companies like IXL ask the Find the Derangement of An Array coding problem to test a candidate's ability to derive recursive relationships. It evaluates your knowledge of Combinatorics and your ability to optimize a recursive formula into an iterative Dynamic Programming interview pattern. It's a test of recognizing sub-problems within a permutation.

Algorithmic pattern used

This problem is solved using a Recursive/Iterative Formula (Dynamic Programming).

1. Formula Derivation: Let $D(n)$ be the number of derangements for $n$ elements.

• Pick the first element. There are $n-1$ positions it can go to (any position except its own). Let's say it goes to position $i$.
• Now consider element $i$.
  • Case 1: Element $i$ goes to position 1. We have swapped 1 and $i$. We now need to derange the remaining $n-2$ elements.
  • Case 2: Element $i$ goes anywhere except position 1. This is equivalent to deranging $n-1$ elements.

1. Final Formula: $D(n) = (n - 1) imes (D(n - 1) + D(n - 2))$.
2. Base Cases: $D(1) = 0, D(2) = 1$.

Example explanation

$n = 3$ (Array: [1, 2, 3])

1. $D(1) = 0$
2. $D(2) = 1$ (Only [2, 1] is a derangement)
3. $D(3) = (3 - 1) imes (D(2) + D(1)) = 2 imes (1 + 0) = 2$. The derangements of [1, 2, 3] are [2, 3, 1] and [3, 1, 2].

Common mistakes candidates make

• Recursive TLE: Implementing the formula using simple recursion without memoization ($O(2^N)$).
• Integer Overflow: Forgetting to apply the modulo operator at each step of the calculation.
• Off-by-one: Starting the base cases or the loop at the wrong index.

Interview preparation tip

The "Derangement" formula is a famous sequence in mathematics (the subfactorial). Practice deriving recurrence relations for other combinatorial problems like "Staircase" or "Parentheses Matching" to strengthen your Dynamic Programming skills.