Count All Valid Pickup and Delivery Options — Solution

Problem

You have n orders, each with a pickup event Pi and a delivery event Di. Every pickup must happen before its corresponding delivery. Count how many valid orderings of all 2n events exist, and return the answer modulo 10^9 + 7.

For n = 2 (orders P1/D1 and P2/D2):

• Input: n = 2
• Output: 6
• Explanation: The six valid sequences are [P1,P2,D1,D2], [P1,P2,D2,D1], [P2,P1,D1,D2], [P2,P1,D2,D1], [P1,D1,P2,D2], and [P2,D2,P1,D1].

A sequence like [D1,P1,P2,D2] is invalid because D1 appears before P1.

Intuition

Think about building the sequence one order at a time. After placing i-1 orders (occupying 2i-2 slots), there are 2i-1 gaps where you could insert the next pickup. Once the pickup is placed, the delivery must go in one of the slots that comes after it. Counting those choices multiplicatively gives a clean O(n) formula: each new order i multiplies the count by i × (2i - 1).

Solution — Mathematical DP

Build the answer incrementally. For each new order i, count the ways to insert its pickup and delivery into the existing sequence of 2(i-1) items, then multiply into a running total.

1. Start with result = 1 and MOD = 10^9 + 7.
2. For each order index i from 1 to n:
   • After placing i-1 orders, there are 2i total slots (the 2i-2 filled slots plus the 2 we are about to fill).
   • The pickup Pi can go in any of 2i-1 gaps (before, between, or after the existing 2i-2 items).
   • Once Pi is placed, the delivery Di must go in a slot after Pi; on average there are i such positions (the formula i*(2i-1) captures both choices together, derived as (2i)*(2i-1)/2).
   • Multiply result by i * (2i - 1), taken modulo MOD.
3. Return result.

1def countOrders(n: int) -> int:
2    MOD = 10**9 + 7
3    result = 1
4    for order_index in range(1, n + 1):
5        # Ways to slot pickup Pi and delivery Di into the existing sequence.
6        # (2*order_index slots total, pickup before delivery) = order_index * (2*order_index - 1)
7        result = result * order_index * (2 * order_index - 1) % MOD
8    return result

Time: O(n) — one multiplication per order.

Space: O(1) — only a running product is kept.

Complexity Summary

Common Mistakes

• Using integer overflow without modular reduction: For n=500 the intermediate product order_index * (2*order_index - 1) fits in 64 bits, but the running result does not — apply % MOD after each multiplication, not only at the end.
• Starting the loop at i=0 instead of i=1: The formula gives 0 * (-1) = 0 at i=0, which zeroes out the entire result. The first meaningful order is i=1.
• Forgetting that the modular result must stay as the running total: A common bug is computing result = (result * factor) in Python without % MOD, which produces a astronomically large integer that still gives the right answer but defeats the purpose of modular arithmetic and is extremely slow for large n.
• Deriving the per-step factor incorrectly as (2i) * (2i-1) instead of i * (2i-1): The full factor for inserting two ordered items into 2i positions is (2i choose 2) = i*(2i-1), not (2i)*(2i-1). Forgetting to divide by 2 double-counts every (pickup, delivery) pair.
• Confusing this with a pure permutation problem: n! counts the orderings of n distinguishable orders with no pickup/delivery constraint. Adding the Pi-before-Di constraint cuts each order's choices roughly in half, producing the (2n-1)!! factor rather than (2n)!.

Related Problems

• unique-paths — another combinatorics problem where the answer derives from counting constrained arrangements
• permutations — foundational enumeration of arrangements, the unconstrained baseline this problem builds on
• combination-sum-ii — constrained selection problems solved by thinking about choices at each step
• permutation-sequence — counting and indexing into constrained permutations using factorials
• unique-binary-search-trees — the Catalan number recurrence follows the same multiplicative logic of counting constrained structural arrangements