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).
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: n = 1 Output: 1 Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
Example 2:
Input: n = 2 Output: 6 Explanation: All possible orders: (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1). This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.
Example 3:
Input: n = 3 Output: 90
Constraints:
1 <= n <= 500Problem Overview: Given n pickup and delivery orders, count how many valid sequences exist such that each delivery D_i happens only after its corresponding pickup P_i. The answer grows quickly, so results are returned modulo 1e9 + 7. The challenge is counting valid permutations while respecting ordering constraints.
Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))
This method models the process using two variables: remaining pickups and remaining deliveries. At any step, you can place a pickup if any remain, or place a delivery if its pickup has already been used. The recursive state dp(p, d) represents the number of valid sequences with p pickups and d deliveries left. Each state branches into placing a pickup (p choices) or a valid delivery (d - p choices because those pickups are already done). Memoization stores computed states to avoid repeated work. This approach clearly shows the combinatorial structure and works well for learning recursion and dynamic programming.
Approach 2: Iterative Combinatorics Formula (Time: O(n), Space: O(1))
A mathematical observation leads to a much simpler solution. When adding the i-th order, there are 2i - 1 possible positions to insert the delivery relative to the pickup while preserving validity. The number of ways to place the pickup among current slots gives i choices, producing the recurrence f(i) = f(i-1) * i * (2i - 1). Iterating from 1 to n and multiplying these terms builds the result efficiently. This converts the counting problem into a direct formula using ideas from math and combinatorics. Only a running product and modulo operations are required.
Recommended for interviews: The combinatorics iteration is the expected optimal solution. It runs in O(n) time with constant space and shows strong pattern recognition. The recursive DP approach is still valuable during discussion because it demonstrates how to model constraints with state transitions before simplifying the counting mathematically.
This approach leverages recursion with memoization to calculate the number of valid sequences. The main idea is to determine how many ways we can arrange pickups and deliveries by handling one order at a time.
This Python function uses a recursive helper function dp(p, d) that tracks how many pickups and deliveries are remaining. If both pickups and deliveries are zero, it returns 1 as a valid sequence is formed. Otherwise, it calculates the possible sequences either by picking up an order or delivering an order, avoiding violating the sequence rule.
Time Complexity: O(N^2), where N is the number of orders, due to overlapping subproblems.
Space Complexity: O(N^2) due to storing results in the memoization dictionary.
This approach uses a combinatorial method by calculating factorial operations iteratively to compute the number of valid sequences. It simplifies the problem by deriving a general formula.
This C++ solution iteratively applies a combinatorial formula that derives from possible positioning of deliveries after pickups. It computes using factorial increases corresponding to the number of current orders.
C++
JavaScript
Time Complexity: O(N), where N is the number of orders.
Space Complexity: O(1), as we only maintain a constant amount of extra space.
We define f[i] as the number of all valid pickup/delivery sequences for i orders. Initially, f[1] = 1.
We can choose any of these i orders as the last delivery order D_i, then its pickup order P_i can be at any position in the previous 2 times i - 1, and the number of pickup/delivery sequences for the remaining i - 1 orders is f[i - 1], so f[i] can be expressed as:
$
f[i] = i times (2 times i - 1) times f[i - 1]
The final answer is f[n].
We notice that the value of f[i] is only related to f[i - 1], so we can use a variable instead of an array to reduce the space complexity.
The time complexity is O(n), where n is the number of orders. The space complexity is O(1)$.
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(N^2), where N is the number of orders, due to overlapping subproblems. |
| Iterative Approach with Combinatorics | Time Complexity: O(N), where N is the number of orders. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DP with Memoization | O(n^2) | O(n^2) | When explaining the state transitions or deriving the counting logic step‑by‑step |
| Iterative Combinatorics Formula | O(n) | O(1) | Optimal solution for interviews and production due to simple math formula |
Count all Valid Pickup and Delivery Options - Leetcode 1359 - Python • NeetCodeIO • 12,107 views views
Watch 9 more video solutions →Practice Count All Valid Pickup and Delivery Options with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor