⚡Flashcard Drill➔
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

  1. Insert orders one at a time and count the positions the new pickup and delivery can occupy.
  2. When adding the i-th order to a sequence of 2(i-1) events, the pickup has 2i - 1 valid slots and the delivery must follow it, giving i valid delivery placements.
  3. The recurrence is therefore f(i) = f(i-1) * (2i - 1) * i, with f(1) = 1.
  4. The closed form (2n)! / 2^n is 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^n directly: the factorial overflows and exact division would need modular inverses.
  • Omitting the factor i: the recurrence is f(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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems