Count All Valid Pickup and Delivery Options — Hard Problem & Solution

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.

Difficulty: Hard
Topics: Math, Dynamic Programming, 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

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 i from 1 to n, set f(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 = 1 gives 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue