Problem Explanation

In this problem, a derangement is defined as a permutation of the elements of a set, such that no element appears in its original position.

Here we are given a sorted array with n integers from 1 to n. We are required to find out the total number of derangements that can be formed from this array. In other words, we need to find out the total number of ways we can rearrange the array elements such that no element ends up in its original position. The output may be extremely large so we are to return the output mod 10⁹ + 7.

For example, the input is 3, corresponding to the original array [1,2,3], we can count 2 derangements [2,3,1] and [3,1,2].

Solution walk-through

The solution makes use of dynamic programming to find the number of derangements for a given array. This approach is based on the fact that the number of derangements for n is equal to (n - 1) * (derangements(n - 1) + derangements(n - 2)).

In the solution, we define a dp vector to cache the number of derangements for each n. Then we apply the formula mentioned above recursively, and the recursive process stops when n equals 0 or 1, in which case the number of derangements is 1 or 0, respectively.

This solution's time complexity is O(n), and the space complexity is also O(n).

Python Solution

1
2python
3class Solution:
4    kMod = 10**9 + 7
5    dp = [1, 0]
6    def findDerangement(self, n: int) -> int:
7        while len(self.dp) <= n:
8            self.dp.append((len(self.dp) - 1) * (self.dp[-1] + self.dp[-2]) % self.kMod)
9        return self.dp[n]

Java Solution:

1
2java
3public class Solution {
4    private int find(int i, int[] dp) {
5        if (i == 0) return 1; 
6        if (i == 1) return 0; 
7        if (dp[i] != 0) return dp[i]; 
8        return dp[i] = (int)(((i - 1L) * (find(i - 1, dp) + find(i - 2, dp)) % (10**9 + 7)));
9    }
10    
11    public int findDerangement(int n) {
12        int[] dp = new int[n + 1];
13        return find(n, dp);
14    }
15}

JavaScript Solution

1
2javascript
3class Solution {
4    findDerangement(n) {
5        let dp = new Array(n + 1).fill(0);
6        dp[0] = 1;
7        dp[1] = 0;
8        for(let i = 2; i <= n; ++i) {
9            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % (10**9 + 7);
10        }
11        return dp[n];
12    }
13}

C++ Solution

1
2cpp
3class Solution {
4public:
5    static constexpr int kMod = 1000000007;
6    vector<int> dp;
7
8    int find(int i) {
9        if (i == 0)
10            return 1;
11        if (i == 1)
12            return 0;
13        if (dp[i])
14            return dp[i];
15        return dp[i] = (i - 1L) * (find(i - 1) + find(i - 2)) % kMod;
16    }
17
18    int findDerangement(int n) {
19        dp.resize(n + 1);
20        return find(n);
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int FindDerangement(int n) {
5        if (n == 1) { return 0; }
6        if (n == 2) { return 1; }
7        int MOD = 1000000007;
8        long[] dp = new long[n + 1];
9        dp[1] = 0;
10        dp[2] = 1;
11        for (int i = 3; i <= n; i++) {
12            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % MOD;
13        }
14        return (int)dp[n];
15    }
16}

Swift Solution:

1
2swift
3class Solution {
4    func findDerangement(_ n: Int) -> Int {
5        if n == 0 { return 1 }
6        if n == 1 { return 0 }
7        
8        var dp = Array(repeating: 0, count: n + 1)
9        dp[0] = 1
10        dp[1] = 0
11        
12        for i in 2 ..< n + 1 {
13            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % 1_000_000_007
14        }
15        
16        return dp[n]
17    }
18}

Ruby Solution:

1
2ruby
3class Solution
4    MOD = 10**9 + 7
5    def find_derangement(n)
6        dp = [1, 0]
7        2.upto(n) do |i|
8            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % MOD
9        end
10        dp[n]
11    end
12end

Explanation

These solutions start by checking for the base cases (n=0,n=1). For n>1, they implement the recursive derangement formula (n - 1) * (derangement(n - 1) + derangement(n - 2)), using dynamic programming to store (dp[i]) and reuse previous computed values. Afterwards, the number of total derangements for the input (n) is returned. They all run in O(n) time and use O(n) space.

These solutions can help in problems that involve combinatorial mathematics, permutations, and rearrangements, making them vital to certain areas such as cryptography, coding theory, and graph theory. At the same time, they demonstrate the use of dynamic programming to avoid redundant computations, thus optimizing the solution.