634. Find the Derangement of An Array

Problem Description

In the classical branch of mathematics known as combinatorics, a derangement is a specific type of permutation. In a derangement, the array elements are permuted in such a way that no element stays in its original position. The given problem asks us to find out how many derangements are possible for a set of n unique elements initially in ascending order from 1 to n. The result should be modulo 10^9 + 7 to avoid handling very large numbers. This means we must do the arithmetic operations and return the final result of the derangements count modulo 10^9 + 7.

Intuition

Calculating the number of derangements, which are also known as !n (or subfactorials), for a given n, can be approached using dynamic programming. The mathematical property governing derangements is usually expressed by the recursive formula:

!n = (n - 1) * (!(n - 1) + !(n - 2))

This formula tells us that the number of derangements for n elements can be found by multiplying n - 1 with the sum of derangements for n - 1 elements and n - 2 elements.

To solve this using dynamic programming, we can start with a base case and build up to the solution for n. For n=1, there are no derangements since the single element will always be in its place. For n=2, there is exactly 1 derangement (2,1). Using these starting points, we can calculate the number of derangements for each successive value of n until we reach our desired number.

In the provided solution, the iterative method is used. Two variables a and b are used. They represent the count of derangements for i-2 and i-1 respectively. Initially, a is set to 1 and b to 0, representing the base cases for n=1 (no derangements) and n=2 (one derangement).

As we iterate from 2 up to n:

The new value of b is the count of derangements for the current i, which uses the recursion relation.
The current value of a is updated to the previous b, preparing for the next iteration.

Finally, b gives us the count of derangements for n modulo 10^9 + 7.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming to efficiently compute the number of derangements for a given number n. Here is a breakdown of the implementation step by step:

We define the modulo mod = 10**9 + 7 to ensure all operations are performed under this modulo to prevent integer overflow.
We start with two variables a and b which will hold the counts of derangements for i-2 and i-1 respectively, as per the recursive formula. Initially a equals 1 (for i=0 since there are no derangements) and b equals 0 (for i=1 which would be 1 derangement, but the array is 0-indexed, so b is initialized as 0 to correct for this offset).
A for-loop is started, ranging from i = 2 to i = n + 1. This loop will iterate through each number i and calculate the number of derangements based on the previously calculated values.
Inside the loop, first, the current value for a (which is the derangement count for i-2) is assigned to b. This is because after this iteration, b (the derangement count for i-1) needs to be updated for the next iteration.
The new value of b is then calculated using the derangement formula: (i - 1) * (a + b) % mod. This represents !i = (i - 1) * (![i - 1] + ![i - 2]), where !i is the number of derangements for i.
The modulo operation is applied to ensure the result stays within the bounds of integer values defined by 10^9 + 7.
The loop continues until it calculates the derangement for i = n.
Finally, the function returns the value of b, which, at the end of the loop, holds the number of derangements for n, modulo 10^9 + 7.

No additional data structures are needed for this computation other than the two variables a and b, because the state of the current calculation only depends on the previous two states. This solution is space-efficient, utilizing O(1) space, and time-efficient with a complexity of O(n) as it requires a single pass from 2 to n.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach using n=4. We want to find out how many derangements are possible for an array of [1, 2, 3, 4].

Initialize mod as 10^9 + 7 for modulo operations.
Start with a = 1 and b = 0. This is because we're using 0-based indexing (for i=2, there is 1 derangement (2,1), hence a = 1; and for i=1, there are no derangements, hence b = 0).
Begin iterating from i = 2 to i = 4.
- For i = 2, we set the previous b to a, so a = 0 (from the previous b value).
- Now, calculate the new b as (i - 1) * (a + b) % mod, which is (2 - 1) * (0 + 0) % mod = 1.
Move to i = 3.
- Set a = 1 (old value of b).
- Now, calculate b as (i - 1) * (a + b) % mod, which is (3 - 1) * (1 + 1) % mod = 4. There are four derangements for [1, 2, 3]: (2, 3, 1), (3, 1, 2), (2, 1, 3), and (3, 2, 1).
For i = 4, the process is similar.
- Set a = 4 (old value of b).
- Calculate b as (i - 1) * (a + b) % mod, which is (4 - 1) * (4 + 1) % mod = 15.
After the loop ends, b holds the number of derangements for n = 4, which is 15, modulo 10^9 + 7.

Thus, the final answer for the number of derangements when n=4 is 15, under the modulo 10^9 + 7. The solution uses only two variables and one loop, making it very space and time efficient.

Solution Implementation

1class Solution:
2    def findDerangement(self, n: int) -> int:
3        # Initialize a modulo constant as per the problem statement
4        mod = 10**9 + 7
5      
6        # Initialize variables to store results of subproblems.
7        # 'prev_two' holds the (i-2)th derangement number, 'prev_one' for (i-1)th.
8        prev_two, prev_one = 1, 0
9      
10        # Loop through numbers 2 to n to calculate the derangement of n using the
11        # recursive relation: D(i) = (i - 1) * (D(i - 1) + D(i - 2))
12        for i in range(2, n + 1):
13            # 'current' holds the current derangement number being calculated
14            current = ((i - 1) * (prev_two + prev_one)) % mod
15          
16            # Update 'prev_two' and 'prev_one' for the next iteration.
17            # 'prev_two' becomes 'prev_one', and 'prev_one' becomes 'current'.
18            prev_two, prev_one = prev_one, current
19
20        # 'prev_one' holds the derangement of n, return this value.
21        return prev_one
22

1class Solution {
2    public int findDerangement(int n) {
3        final int MOD = (int) 1e9 + 7; // Define the modulo value as a constant
4        // Initialize the variables to store previous results
5        long previous = 1; // this will eventually hold the derangement count for (i-2)
6        long current = 0; // this will eventually hold the derangement count for (i-1)
7
8        // Iterate from 2 to n to build up the derangement counts
9        for (int i = 2; i <= n; ++i) {
10            // Calculate the derangement count for the current value of i using the recurrence relation
11            // D(n) = (n-1) * (D(n-1) + D(n-2))
12            long next = (i - 1) * (previous + current) % MOD;
13            // Update the previous values for the next iteration
14            previous = current;
15            current = next;
16        }
17
18        // Cast the result to int and return it as the final derangement count for n
19        return (int) current;
20    }
21}
22

1class Solution {
2public:
3    // Function to find the number of derangements (permutations where no element appears in its original position) for a given number n
4    int findDerangement(int n) {
5        long long prevPrev = 1; // Represents the derangement count for n-2, initialized for n = 0 base case
6        long long prev = 0;     // Represents the derangement count for n-1, initialized for n = 1 base case
7        const int MOD = 1e9 + 7; // Modulo value to prevent integer overflow
8
9        // Loop to calculate the derangements for all numbers from 2 to n
10        for (int i = 2; i <= n; ++i) {
11            // Calculate the current derangement count using the recursive formula:
12            // D(n) = (n - 1) * (D(n - 1) + D(n - 2))
13            long long current = (i - 1) * (prevPrev + prev) % MOD;
14          
15            // Shift derangement counts for next iteration
16            prevPrev = prev;
17            prev = current;
18        }
19      
20        // The last computed value is the derangement count for n
21        return prev;
22    }
23};
24

1// Modulo value to prevent integer overflow
2const MOD = 1e9 + 7;
3
4// Function to find the number of derangements (permutations where no element appears in its original position) for a given number n
5function findDerangement(n: number): number {
6    let prevPrev: bigint = BigInt(1); // Represents the derangement count for n-2, initialized for n = 0 base case
7    let prev: bigint = BigInt(0);     // Represents the derangement count for n-1, initialized for n = 1 base case
8
9    // Loop to calculate the derangements for all numbers from 2 to n
10    for (let i = 2; i <= n; ++i) {
11        // Calculate the current derangement count using the recursive formula:
12        // D(n) = (n - 1) * (D(n - 1) + D(n - 2))
13        let current: bigint = BigInt(i - 1) * (prevPrev + prev) % BigInt(MOD);
14
15        // Shift derangement counts for next iteration
16        prevPrev = prev;
17        prev = current;
18    }
19  
20    // The last computed value is the derangement count for n
21    // Conversion of bigint to number while ensuring it fits within the safe integer range for JavaScript
22    return Number(prev % BigInt(MOD));
23}
24

Time and Space Complexity

The code provided calculates the number of derangements of n items, which is a permutation where no element appears in its original position.

Time Complexity

The time complexity of the given function is O(n). This is determined by the for loop, which iterates from 2 to n+1, making exactly n-1 iterations. Each iteration involves a constant amount of work, consisting of basic arithmetic operations and a modulo operation, all of which have a time complexity of O(1). Hence, the overall time complexity is the product of the number of iterations (n-1) and the time complexity of the work done per iteration O(1), leading to an O(n) time complexity.

Space Complexity

The space complexity of the function is O(1) because it uses a fixed amount of extra space. Regardless of the input size n, it only maintains a constant number of variables (a, b, mod, and i) that do not depend on the size of the input. This implies that the memory used does not scale with n, making the space complexity constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know