Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Find the Derangement of An Array solution and explanation

MediumDynamic ProgrammingMath4 min read41.9% acceptanceUpdated 23 Mar 2026Premium elsewhere, free here
Asked atIxl
Practise Find the Derangement of An Array
9:32
[DP]634.Find the Derangement of An ArrayXIAOLONG · 9:32 · 642 viewsWatch on YouTube
4 more videos on this problem
  1. [DP]634.Find the Derangement of An ArrayXIAOLONG · 9:32 · 642 views
  2. 634 Find the Derangement of An Arraychen xiang · 10:12 · 604 views
  3. 634. Find the Derangement of An Array (Leetcode Medium)Programming Live with Larry · 18:13 · 335 views
  4. Leetcode 0634. Find the Derangement of An ArrayFearless Learner · 13:00 · 80 views
  5. LeetCode 634: Find the Derangement of An ArrayAlitaCode · 27:45 · 8 views

The problem

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

You are given an integer n. There is originally an array consisting of n integers from 1 to n in ascending order, return the number of derangements it can generate. Since the answer may be huge, return it modulo 109 + 7.

Example 1:

Input: n = 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Example 2:

Input: n = 2
Output: 1

Constraints:

  • 1 <= n <= 106

Approach overview

Problem Overview: You are given an integer n representing the size of an array containing numbers 1..n. The task is to count how many permutations exist where no element appears in its original position. This is called a derangement. The result must be returned modulo 1e9 + 7.

Approach 1: Dynamic Programming (O(n) time, O(n) space)

Derangements follow a classic recurrence relation from math and dynamic programming. If D(n) represents the number of derangements for size n, the recurrence is D(n) = (n - 1) * (D(n - 1) + D(n - 2)). The reasoning: choose a position for element 1 among n-1 spots. If the swapped element goes to position 1, the remaining array behaves like D(n-2). Otherwise, it behaves like D(n-1). Build a DP array where each entry stores the derangement count for that size. Start with base cases D(1) = 0 and D(2) = 1, then iterate from 3 to n applying the recurrence and taking modulo 1e9+7. This approach is straightforward and mirrors the mathematical definition directly. Time complexity is O(n) because you compute each state once, and space complexity is O(n) for the DP table.

Approach 2: Dynamic Programming (Space Optimization) (O(n) time, O(1) space)

The recurrence only depends on the previous two values: D(n-1) and D(n-2). Storing the entire DP table is unnecessary. Instead, keep two variables representing these states and update them while iterating from 3 to n. Each iteration computes the next value using the same recurrence and shifts the variables forward. This reduces auxiliary memory to constant space while preserving the same O(n) time complexity. The modulo operation still applies during each multiplication to prevent overflow.

This version is typically preferred in production or competitive programming because it uses minimal memory and still expresses the mathematical recurrence clearly. The logic remains identical to the full DP version, but with two rolling variables instead of an array.

Recommended for interviews: Start by explaining the recurrence relation for derangements. That shows understanding of the combinatorial structure of the problem. Implement the O(n) dynamic programming solution first for clarity, then mention the constant-space optimization. Interviewers expect the recurrence-based DP because brute force permutation generation would take O(n!) time and is infeasible even for moderate n.

Approach 1: Dynamic Programming

We define f[i] as the number of derangement of an array of length i. Initially, f[0] = 1, f[1] = 0. The answer is f[n].

For an array of length i, we consider where to place the number 1. Suppose it is placed in the j-th position, where there are i-1 choices. Then, the number j has two choices:

  • Placed in the first position, then the remaining i - 2 positions have f[i - 2] derangements, so there are a total of (i - 1) times f[i - 2] derangements;
  • Not placed in the first position, which is equivalent to the derangement of an array of length i - 1, so there are a total of (i - 1) times f[i - 1] derangements.

In summary, we have the following state transition equation:

$ f[i] = (i - 1) times (f[i - 1] + f[i - 2])

The final answer is f[n]. Note the modulo operation in the answer.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.

class Solution:
    def findDerangement(self, n: int) -> int:
        mod = 10**9 + 7
        f = [1] + [0] * n
        for i in range(2, n + 1):
            f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % mod
        return f[n]
class Solution {
    public int findDerangement(int n) {
        long[] f = new long[n + 1];
        f[0] = 1;
        final int mod = (int) 1e9 + 7;
        for (int i = 2; i <= n; ++i) {
            f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % mod;
        }
        return (int) f[n];
    }
}
class Solution {
public:
    int findDerangement(int n) {
        long long f[n + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        const int mod = 1e9 + 7;
        for (int i = 2; i <= n; i++) {
            f[i] = (i - 1LL) * (f[i - 1] + f[i - 2]) % mod;
        }
        return f[n];
    }
};
func findDerangement(n int) int {
	f := make([]int, n+1)
	f[0] = 1
	const mod = 1e9 + 7
	for i := 2; i <= n; i++ {
		f[i] = (i - 1) * (f[i-1] + f[i-2]) % mod
	}
	return f[n]
}
Try this approach in the editor

Approach 2: Dynamic Programming (Space Optimization)

We notice that the state transition equation only relates to f[i - 1] and f[i - 2]. Therefore, we can use two variables a and b to represent f[i - 1] and f[i - 2] respectively, thereby reducing the space complexity to O(1).

class Solution:
    def findDerangement(self, n: int) -> int:
        mod = 10**9 + 7
        a, b = 1, 0
        for i in range(2, n + 1):
            a, b = b, ((i - 1) * (a + b)) % mod
        return b
class Solution {
    public int findDerangement(int n) {
        final int mod = (int) 1e9 + 7;
        long a = 1, b = 0;
        for (int i = 2; i <= n; ++i) {
            long c = (i - 1) * (a + b) % mod;
            a = b;
            b = c;
        }
        return (int) b;
    }
}
class Solution {
public:
    int findDerangement(int n) {
        long long a = 1, b = 0;
        const int mod = 1e9 + 7;
        for (int i = 2; i <= n; ++i) {
            long long c = (i - 1) * (a + b) % mod;
            a = b;
            b = c;
        }
        return b;
    }
};
func findDerangement(n int) int {
	a, b := 1, 0
	const mod = 1e9 + 7
	for i := 2; i <= n; i++ {
		a, b = b, (i-1)*(a+b)%mod
	}
	return b
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming–
Dynamic Programming (Space Optimization)–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (DP array)O(n)O(n)Best for understanding the recurrence and debugging intermediate values
Dynamic Programming (Space Optimized)O(n)O(1)Preferred in interviews and competitive programming when memory usage matters

Frequently asked questions

Is Find the Derangement of An Array easy or hard?

Find the Derangement of An Array is generally rated Medium. The implementation is short, but recognizing the correct recurrence relation and connecting the problem to combinatorial derangements requires some mathematical insight.

Find the Derangement of An Array Python/Java solution

Python, Java, C++, and Go implementations all follow the same recurrence relation for derangements. Each iteration computes (n - 1) * (prev1 + prev2) modulo 1e9+7 while updating the previous states until reaching n.

How to solve Find the Derangement of An Array in O(n)?

Use the recurrence D(n) = (n - 1) * (D(n - 1) + D(n - 2)). Initialize base cases D(1) = 0 and D(2) = 1, then iterate from 3 to n computing each value modulo 1e9+7. This iterative dynamic programming approach computes the answer in linear time.

What is the best approach for Find the Derangement of An Array?

The optimal approach uses a dynamic programming recurrence: D(n) = (n - 1) * (D(n - 1) + D(n - 2)). This computes the number of derangements iteratively in O(n) time. With a rolling two-variable optimization, the space complexity can be reduced to O(1).

Is Find the Derangement of An Array asked at Google/Amazon/Meta?

Derangement counting appears in interviews related to combinatorics, probability, and dynamic programming. Variants of this problem have been asked at companies like Google and Amazon to test mathematical reasoning and recurrence-based DP skills.

What data structure is used in Find the Derangement of An Array?

The solution primarily uses dynamic programming. Either a DP array stores values from 1 to n, or two variables track the previous states for a space-optimized implementation. No complex data structures are required.

What is the time complexity of Find the Derangement of An Array?

The dynamic programming solution runs in O(n) time because each derangement value from 3 to n is computed once using constant-time arithmetic operations. Space complexity is O(n) with a DP array or O(1) with the optimized version.

Comments

Now write it yourselfClose this page and solve Find the Derangement of An Array in the editor, without looking.
Practise Find the Derangement of An Array