Find the Derangement of An Array — LeetCode 634 Python Solution
MediumLeetCode PremiumMathDynamic ProgrammingCombinatorics
- Problem
- #634
- Pattern
- Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
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.
Example
- Input
- n = 3
- Output
- 2
- Explanation
- The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
Python solution
Python
def findDerangement(n: int) -> int:
mod = 10**9 + 7
if n == 1:
return 0
dp0, dp1 = 1, 0
for i in range(2, n + 1):
dp0, dp1 = dp1, (i - 1) * (dp0 + dp1) % mod
return dp1Complexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the array |
| Space | O(1) auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 634. Find the Derangement of An Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
LeetCode 62Unique PathsMediumLeetCode 458Poor PigsHardLeetCode 920Number of Music PlaylistsHardLeetCode 1359Count All Valid Pickup and Delivery OptionsHardLeetCode 1467Probability of a Two Boxes Having The Same Number of Distinct BallsHardLeetCode 1569Number of Ways to Reorder Array to Get Same BSTHard
Frequently asked questions
- How hard is LeetCode 634. Find the Derangement of An Array?
- LeetCode 634. Find the Derangement of An Array is rated Medium on LeetCode.
- What is the time complexity of LeetCode 634. Find the Derangement of An Array?
- The Python solution on this page runs in O(n), where n is the length of the array.
- What is the space complexity of LeetCode 634. Find the Derangement of An Array?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 634. Find the Derangement of An Array cover?
- LeetCode 634. Find the Derangement of An Array is tagged Math, Dynamic Programming and Combinatorics on LeetCode.
- Is LeetCode 634. Find the Derangement of An Array a premium problem?
- Yes. LeetCode 634. Find the Derangement of An Array is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.