Count All Valid Pickup and Delivery Options — Solution
Count All Valid Pickup and Delivery Options solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count All Valid Pickup and Delivery Options is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n orders, each with a pickup and a delivery. Count the sequences of all 2n events in which every delivery comes after its own pickup.
Return the count modulo 10⁹ + 7.
Example 1
Input: n = 1
Output: 1
Explanation: Only `P1, D1`.
Example 2
Input: n = 2
Output: 6
Explanation: Six of the 24 orderings respect both constraints.
Example 3
Input: n = 3
Output: 90
Constraints
1 <= n <= 500
Hints for Count All Valid Pickup and Delivery Options
Hint 1
Build the answer one order at a time: suppose you have a valid sequence for
n - 1orders, of length2n - 2.Hint 2
Inserting the new pickup has
2n - 1slots; the delivery must then go after it.Hint 3
Count the delivery slots and you get a clean recurrence.
How to solve Count All Valid Pickup and Delivery Options
Insert one order at a time. A valid arrangement of n-1 orders has 2n-2 events and 2n-1 gaps. Place the new pickup in any gap; that splits the sequence so the delivery has some number of legal positions after it — summing over the pickup's choices gives exactly (2n-1) · n new arrangements per old one.
Approach
- Start with
f(0) = 1. - For each
ifrom 1 ton, setf(i) = f(i-1) · (2i - 1) · i, modulo 10⁹ + 7. - Return
f(n).
Why it works
The (2i-1) · i factor is the neat part. Naively, the new pair can be placed in C(2i, 2) ordered ways among 2i slots, which is i(2i-1) — and exactly half of all placements have the delivery before the pickup, so the valid count is (2i)! / (2^i) overall, matching the recurrence. Deriving it as "insert the pickup, then count legal delivery slots" is the version that generalises to related problems.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The two factors must each be reduced modulo 10⁹ + 7; their product exceeds 32 bits otherwise.
- The answer is not
(2n)!— half of every pair's orderings are invalid. n = 1gives 1, not 2.
Reference solution
Python
def countOrders(n: int) -> int:
MOD = 10**9 + 7
answer = 1
for i in range(1, n + 1):
answer = answer * (2 * i - 1) % MOD
answer = answer * i % MOD
return answerJava
public static int countOrders(int n) {
final long MOD = 1000000007L;
long answer = 1;
for (int i = 1; i <= n; i++) {
answer = answer * (2L * i - 1) % MOD;
answer = answer * i % MOD;
}
return (int) answer;
}C++
int countOrders(int n) {
const long long MOD = 1000000007LL;
long long answer = 1;
for (int i = 1; i <= n; i++) {
answer = answer * (2LL * i - 1) % MOD;
answer = answer * i % MOD;
}
return (int) answer;
}JavaScript
var countOrders = function(n) {
var MOD = 1000000007;
var answer = 1;
for (var i = 1; i <= n; i++) {
answer = (answer * (2 * i - 1)) % MOD;
answer = (answer * i) % MOD;
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming