Count All Valid Pickup and Delivery Options - Video Solutions

Problem Overview: Given n pickup and delivery orders, count how many valid sequences exist such that each delivery D_i happens only after its corresponding pickup P_i. The answer grows quickly, so results are returned modulo 1e9 + 7. The challenge is counting valid permutations while respecting ordering constraints.

Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))

This method models the process using two variables: remaining pickups and remaining deliveries. At any step, you can place a pickup if any remain, or place a delivery if its pickup has already been used. The recursive state dp(p, d) represents the number of valid sequences with p pickups and d deliveries left. Each state branches into placing a pickup (p choices) or a valid delivery (d - p choices because those pickups are already done). Memoization stores computed states to avoid repeated work. This approach clearly shows the combinatorial structure and works well for learning recursion and dynamic programming.

Approach 2: Iterative Combinatorics Formula (Time: O(n), Space: O(1))

A mathematical observation leads to a much simpler solution. When adding the i-th order, there are 2i - 1 possible positions to insert the delivery relative to the pickup while preserving validity. The number of ways to place the pickup among current slots gives i choices, producing the recurrence f(i) = f(i-1) * i * (2i - 1). Iterating from 1 to n and multiplying these terms builds the result efficiently. This converts the counting problem into a direct formula using ideas from math and combinatorics. Only a running product and modulo operations are required.

Recommended for interviews: The combinatorics iteration is the expected optimal solution. It runs in O(n) time with constant space and shows strong pattern recognition. The recursive DP approach is still valuable during discussion because it demonstrates how to model constraints with state transitions before simplifying the counting mathematically.