LeetCode 634: Find the Derangement of An Array Solution
Master LeetCode problem 634 (Find the Derangement of An Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
634. Find the Derangement of An Array
Problem Explanation
Explanation
To find the derangement of an array, we need to find a permutation of the array where no element appears in its original position. This can be solved using dynamic programming. We can define the derangement of an array of size n as the number of ways to rearrange the elements such that no element appears in its original position.
We can use the principle of inclusion-exclusion to compute the derangement for each element. Let dp[i] represent the number of derangements for an array of size i.
The recursive formula for computing dp[i] is:
dp[i] = (i-1) * (dp[i-1] + dp[i-2])
Solution Code
class Solution {
public int findDerangement(int n) {
if (n <= 1) {
return 0;
}
long dp1 = 0, dp2 = 1;
for (int i = 3; i <= n; i++) {
long dp = (i - 1) * (dp1 + dp2) % 1000000007;
dp1 = dp2;
dp2 = dp;
}
return (int)dp2;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 634 (Find the Derangement of An Array)?
This page provides optimized solutions for LeetCode problem 634 (Find the Derangement of An Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 634 (Find the Derangement of An Array)?
The time complexity for LeetCode 634 (Find the Derangement of An Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 634 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 634 in Java, C++, or Python.