Count All Valid Pickup and Delivery Options — LeetCode 1359 Python Solution
HardMathDynamic ProgrammingCombinatorics
- Problem
- #1359
- Pattern
- Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given n orders, each order consists of a pickup and a delivery service. Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).
Example
- Input
- n = 1
- Output
- 1
- Explanation
- Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
Python solution
Python
class Solution:
def countOrders(self, n: int) -> int:
mod = 10**9 + 7
f = 1
for i in range(2, n + 1):
f = (f * i * (2 * i - 1)) % mod
return fComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the number of orders |
| Space | O(1) auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1359. Count All Valid Pickup and Delivery Options 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 1467Probability of a Two Boxes Having The Same Number of Distinct BallsHardLeetCode 1569Number of Ways to Reorder Array to Get Same BSTHardLeetCode 1621Number of Sets of K Non-Overlapping Line SegmentsMedium
Frequently asked questions
- How hard is LeetCode 1359. Count All Valid Pickup and Delivery Options?
- LeetCode 1359. Count All Valid Pickup and Delivery Options is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1359. Count All Valid Pickup and Delivery Options?
- The Python solution on this page runs in O(n), where n is the number of orders.
- What is the space complexity of LeetCode 1359. Count All Valid Pickup and Delivery Options?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1359. Count All Valid Pickup and Delivery Options cover?
- LeetCode 1359. Count All Valid Pickup and Delivery Options is tagged Math, Dynamic Programming and Combinatorics on LeetCode.