Count All Valid Pickup and Delivery Options: Combinatorial Counting Pattern

Given n orders, each consisting of a pickup and a delivery service, count all valid pickup/delivery sequences such that delivery i always occurs after pickup i. Return the answer modulo 10^9 + 7.

This is LeetCode 1359: Count All Valid Pickup and Delivery Options, and it is one of the cleanest examples of the combinatorial counting pattern. The technique it teaches applies to any problem where you need to count constrained permutations by building them up one element at a time.

Why this problem matters

Combinatorial counting problems appear frequently in interviews and competitive programming. They test whether you can spot a recurrence hidden inside a constraint. The constraint here ("each delivery must come after its pickup") looks like it might require generating all permutations and filtering, but that approach is far too slow. Instead, you learn to count valid arrangements directly by reasoning about how many choices you have at each step.

This same "insert the next element and count placements" technique shows up in problems about interleaving sequences, arranging parentheses, and counting paths through grids. Once you see the pattern here, you will recognize it in many other contexts.

The key insight

Instead of counting all (2n)! permutations and filtering, build the sequence incrementally. Start with an empty sequence and insert one order at a time. When you insert order i, the existing sequence already has 2(i-1) items, creating 2i - 1 gaps (including before the first item and after the last item). You place pickup Pi in one of those gaps, and then delivery Di must go in one of the gaps that comes after Pi.

If Pi goes in the first gap, Di has 2i - 1 choices. If Pi goes in the second gap, Di has 2i - 2 choices. And so on, down to Pi in the last gap where Di has exactly 1 choice (right after Pi). The total number of valid placements for order i is:

(2i - 1) + (2i - 2) + ... + 1 = i * (2i - 1)

Multiply across all orders from 1 to n to get the final answer.

The solution

def count_orders(n: int) -> int:
    MOD = 10**9 + 7
    result = 1
    for i in range(1, n + 1):
        result = result * i * (2 * i - 1) % MOD
    return result

The function starts with result = 1, representing the empty sequence. Then for each order i from 1 to n, it multiplies by i * (2 * i - 1), which is the number of valid ways to insert the i-th pickup-delivery pair into the existing sequence. The modulo operation keeps the number from overflowing.

That is the entire solution. No recursion, no memoization table, no data structures. Just a single loop that multiplies a running product.

Visual walkthrough

Let's trace through the insertion logic for n = 1, n = 2, and n = 3 to see how the formula emerges from concrete placements.

The pattern is clear: each new order multiplies the count by i * (2i - 1). For n = 3, that gives 1 * 6 * 15 = 90. The formula captures the exact number of ways to slot each new pickup-delivery pair into the growing sequence while respecting the "pickup before delivery" constraint.

Complexity analysis

Time is O(n) because the loop runs exactly n iterations, and each iteration performs a constant number of multiplications and a modulo operation.

Space is O(1) because we only store a single running product. There is no recursion stack, no DP table, and no auxiliary data structure.

The building blocks

1. Counting insertion positions

The core technique is recognizing that a sequence of k items has k + 1 gaps where a new item can be inserted. When inserting a pair with an ordering constraint, you place the first element in any gap, then count how many remaining gaps are valid for the second element:

ways_for_order_i = 0
slots = 2 * i - 1
for pos in range(slots):
    ways_for_order_i += slots - pos

This sum slots + (slots-1) + ... + 1 simplifies to slots * (slots + 1) // 2, which equals i * (2*i - 1). Recognizing that a summation collapses into a closed-form formula is a skill you will use across many counting problems.

2. Modular arithmetic in counting problems

When the answer can be astronomically large, the problem asks for it modulo 10^9 + 7. Because we only use multiplication, we can apply the modulo at each step without affecting correctness:

result = result * i * (2 * i - 1) % MOD

This works because (a * b) % m = ((a % m) * (b % m)) % m. You do not need modular inverses here because there is no division. Any time a counting problem uses only addition and multiplication, you can safely take the modulo at every step.

Edge cases

Before submitting, think through these scenarios:

• n = 1: only one order, one valid sequence [P1, D1]. The formula gives 1 * 1 = 1.
• n = 2: the formula gives 1 * 6 = 6, matching the six valid sequences you can enumerate by hand.
• Large n (n = 500): the answer is enormous, but modular arithmetic keeps it within bounds. The loop still finishes in microseconds.
• Overflow concerns: in Python, integers have arbitrary precision, so intermediate overflow is not an issue. In languages like Java or C++, you must apply the modulo after each multiplication to stay within 64-bit integer range.

From understanding to recall

You have seen how the insertion technique transforms a scary-looking permutation problem into a simple loop. The logic is elegant: for each new order, count the valid placements, multiply, and move on. But elegance does not guarantee recall under pressure.

The details that matter are specific. What is the formula for the number of slots? Is it 2i - 1 or 2i + 1? Do you multiply by i * (2i - 1) or (2i - 1) * (2i) / 2? These are the same value, but mixing up the derivation costs time. Spaced repetition drills the formula and the reasoning behind it into your long-term memory, so you do not have to re-derive it on the spot.

Related posts

• Permutations - The foundational backtracking problem for generating all orderings of a set
• Unique Paths - Another combinatorial counting problem solved with dynamic programming on a grid
• Generate Parentheses - Counting valid sequences with ordering constraints, similar to the pickup-before-delivery rule

CodeBricks breaks Count All Valid Pickup and Delivery Options into its combinatorial insertion and modular arithmetic building blocks, then drills them independently with spaced repetition. You type the formula and the loop from scratch until the pattern is automatic. When a counting problem shows up in your interview, the recurrence is already in your fingers.