Problem Description
Given n orders, where each order consists of a pickup and a delivery, count all valid sequences in which each delivery occurs after its corresponding pickup. Since the answer may be large, return it modulo 10^9 + 7.
Key Insights
- The sequence is valid only if for every order i, pickup(i) comes before delivery(i).
- Instead of generating all permutations, use combinatorial reasoning: when inserting the i-th order in an already valid sequence of i-1 orders, there are (2*i-1) choices to place the pickup and delivery such that the pickup precedes the delivery.
- The overall number of valid sequences is the product of choices for each order i: result = ∏ (i * (2*i - 1)), for i = 1 to n.
- Modular arithmetic is used at every multiplication step to handle large numbers.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
We can derive the solution using combinatorial math. When processing the i-th order, think about the available positions where you can place the pickup and delivery. The pickup can be placed in any available position and the delivery must come after the pickup; there are (2i-1) valid ways to do this. However, because each pickup itself is unique, we also factor in i ways (corresponding to the sequence order of the pickup events) naturally by counting products as: product from i = 1 to n of i(2*i - 1). This product is computed while taking the modulo at every step to keep the numbers manageable. No advanced data structure is required, and the approach efficiently computes the answer in a single pass through the orders.