NeetCode #703LC-1359Hard1-D Dynamic Programming
← Back to All Problems#703 · #1359 · Count All Valid Pickup and Delivery Options(有效的快递序列数目)
📌 Problem Statement & Constraints
Given
n orders, each with a pickup P_i and a delivery D_i, count the number of valid sequences of all 2n events in which P_i always precedes D_i, modulo 10^9 + 7. Constraints: 1 <= n <= 500.💡 Core Algorithmic Approaches
- Insert orders one at a time and count the positions the new pickup and delivery can occupy.
- When adding the
i-th order to a sequence of2(i-1)events, the pickup has2i - 1valid slots and the delivery must follow it, givingivalid delivery placements. - The recurrence is therefore
f(i) = f(i-1) * (2i - 1) * i, withf(1) = 1. - The closed form
(2n)! / 2^nis equivalent but the recurrence avoids huge factorials.
💻 Benchmark Python3 Implementation
class Solution:
def countOrders(self, n: int) -> int:
MOD = 10 ** 9 + 7
res = 1
for i in range(2, n + 1):
res = res * (2 * i - 1) * i % MOD
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one multiplication per order.
💾 Space Complexity
O(1): a single accumulator.
⚠️ Interview Pitfalls & Follow-ups
- Computing
(2n)! / 2^ndirectly: the factorial overflows and exact division would need modular inverses. - Omitting the factor
i: the recurrence isf(i-1) * (2i - 1) * i, not just(2i - 1). - Applying the modulo only at the end: intermediate values explode, so reduce every step.
- Returning
(2n)!: that counts every permutation, ignoring the pickup-before-delivery constraint.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.