# Count All Valid Pickup and Delivery Options
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options)
Canonical: https://scaleengineer.com/dsa/problems/count-all-valid-pickup-and-delivery-options
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Acko](https://scaleengineer.com/companies/acko)
---
## Problem
Given `n` orders, each order consists of a pickup and a delivery service.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i). 

Since the answer may be too large, return it modulo 10^9 + 7.

**Example 1:**

**Input:** n = 1
**Output:** 1
**Explanation:** Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

**Example 2:**

**Input:** n = 2
**Output:** 6
**Explanation:** All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

**Example 3:**

**Input:** n = 3
**Output:** 90

**Constraints:**

* `1 <= n <= 500`

# Approaches
## Dynamic Programming
This approach uses recursion with memoization (a top-down dynamic programming technique) to count the valid sequences. We define a function `solve(unpicked, undelivered)` that calculates the number of ways to arrange the remaining items, where `unpicked` is the count of orders yet to be picked up, and `undelivered` is the count of orders that have been picked up but not yet delivered.
**Time:** O(n^2), as there are `n * n` possible states for `(unpicked, undelivered)`, and each state is computed once. · **Space:** O(n^2) for the memoization table `memo`.
**Pros:** Conceptually straightforward application of dynamic programming.; Correctly solves the problem within the time limits for the given constraints.
**Cons:** Less efficient than the mathematical approach in both time and space.; The state representation and recurrence relation might be tricky to derive.
### Explanation
We can think of building the sequence of `2n` events from left to right. At each step, we have two choices: place a pickup or place a delivery.

Let's define a state by `(unpicked, undelivered)`:
- `unpicked`: The number of orders for which we haven't placed the pickup yet.
- `undelivered`: The number of orders for which we have placed the pickup but not the delivery.

At any point, we have `unpicked` pickups we can place and `undelivered` deliveries we can place.

- **Choice 1: Place a Pickup.**
  - We have `unpicked` choices for which pickup to place (e.g., if P1, P2 are unpicked, we can choose either).
  - After placing a pickup, the number of unpicked orders decreases by 1, and the number of undelivered orders increases by 1.
  - The number of ways for this choice is `unpicked * solve(unpicked - 1, undelivered + 1)`.

- **Choice 2: Place a Delivery.**
  - We can only place a delivery for an order whose pickup has already been placed. There are `undelivered` such orders.
  - After placing a delivery, the number of undelivered orders decreases by 1. The number of unpicked orders remains the same.
  - The number of ways for this choice is `undelivered * solve(unpicked, undelivered - 1)`.

This leads to the following recurrence relation:
`solve(unpicked, undelivered) = (unpicked * solve(unpicked - 1, undelivered + 1)) + (undelivered * solve(unpicked, undelivered - 1))`

The base case is `solve(0, 0) = 1`, as there is one way to arrange zero items. We start with the initial call `solve(n, 0)`. To avoid recomputing the same states, we use a 2D array `memo[n+1][n+1]` for memoization.

```java
class Solution {
    long[][] memo;
    int MOD = 1_000_000_007;

    public int countOrders(int n) {
        memo = new long[n + 1][n + 1];
        return (int) solve(n, 0);
    }

    private long solve(int unpicked, int undelivered) {
        if (unpicked == 0 && undelivered == 0) {
            return 1;
        }
        if (unpicked < 0 || undelivered < 0) {
            return 0;
        }
        if (memo[unpicked][undelivered] != 0) {
            return memo[unpicked][undelivered];
        }

        long ans = 0;

        // Option 1: Pick up an order.
        // We have 'unpicked' choices.
        ans += (long) unpicked * solve(unpicked - 1, undelivered + 1);
        ans %= MOD;

        // Option 2: Deliver an order.
        // We have 'undelivered' choices.
        ans += (long) undelivered * solve(unpicked, undelivered - 1);
        ans %= MOD;

        return memo[unpicked][undelivered] = ans;
    }
}
```
### Algorithm
- Create a 2D array `memo` of size `(n+1) x (n+1)` and initialize it with a value indicating that the state has not been computed (e.g., 0 or -1).
- Define a recursive function `solve(unpicked, undelivered)`:
  - If `unpicked == 0` and `undelivered == 0`, it means we have successfully placed all items, so we return 1 (base case).
  - If `unpicked < 0` or `undelivered < 0`, it's an invalid state, so return 0.
  - If `memo[unpicked][undelivered]` is already computed, return the stored value.
  - Calculate the number of ways by placing a pickup: `res = (long)unpicked * solve(unpicked - 1, undelivered + 1)`. We have `unpicked` choices for the pickup.
  - Add the number of ways by placing a delivery: `res += (long)undelivered * solve(unpicked, undelivered - 1)`. We have `undelivered` choices for the delivery.
  - Store the result modulo `10^9 + 7` in `memo[unpicked][undelivered]` and return it.
- The main function initiates the process by calling `solve(n, 0)`.

## Iterative Mathematical Approach
This approach derives a mathematical recurrence relation by considering the placement of one order pair at a time and then solves it iteratively. This is the most efficient method, leveraging combinatorial reasoning to arrive at a simple formula.
**Time:** O(n), as we iterate from 1 to `n` once. · **Space:** O(1), as we only use a few variables to store the intermediate results.
**Pros:** Extremely efficient in both time and space.; Simple and concise implementation.
**Cons:** Requires a combinatorial insight that might not be immediately obvious.
### Explanation
Let `f(n)` be the number of valid pickup and delivery sequences for `n` orders.

**Base Case**: For `n=1`, we have one sequence (P1, D1), so `f(1) = 1`.

**Recurrence Relation**: Let's find a formula for `f(n)` based on `f(n-1)`. Assume we have a valid sequence for `n-1` orders, which has `2(n-1)` positions. Now, we need to insert the new pair, `Pn` and `Dn`. There are `2n` total slots in the final sequence.

Consider the `2n` available slots. We need to choose 2 slots for `Pn` and `Dn`. The number of ways to choose 2 slots is `C(2n, 2)`. Once the slots are chosen, `Pn` must be in the first and `Dn` in the second to maintain validity. So there is only 1 way to place them for each pair of chosen slots. The remaining `2n-2` slots must be filled by the other `n-1` pairs, which can be done in `f(n-1)` ways.

This gives the recurrence:
`f(n) = C(2n, 2) * f(n-1)`
`f(n) = (2n * (2n-1) / 2) * f(n-1)`
`f(n) = n * (2n-1) * f(n-1)`

We can compute `f(n)` iteratively:
- `f(1) = 1`
- `f(2) = f(1) * 2 * (2*2 - 1) = 1 * 2 * 3 = 6`
- `f(3) = f(2) * 3 * (2*3 - 1) = 6 * 3 * 5 = 90`

This can be implemented with a simple loop.

**Alternative Derivation**
The total number of permutations of `2n` distinct items is `(2n)!`. For each of the `n` pairs `(Pi, Di)`, `Pi` must come before `Di`. By symmetry, in exactly half of the permutations, `Pi` is before `Di`. Since there are `n` such independent constraints, we divide by 2 for each pair.
Total valid sequences = `(2n)! / 2^n`.
This can be calculated as `(1 * 3 * 5 * ... * (2n-1)) * n!`, which is equivalent to the iterative calculation from the recurrence.

```java
class Solution {
    public int countOrders(int n) {
        long ans = 1;
        int MOD = 1_000_000_007;

        for (int i = 1; i <= n; i++) {
            // For the i-th pair (Pi, Di), we have 2i-1 previous items.
            // Total slots available are 2i.
            // Ways to choose 2 slots for Pi and Di is C(2i, 2) = i * (2i - 1).
            // We multiply this with the arrangements of previous i-1 pairs.
            // ans for i = (ans for i-1) * i * (2i-1)
            ans = ans * i;
            ans %= MOD;
            ans = ans * (2L * i - 1);
            ans %= MOD;
        }
        
        return (int) ans;
    }
}
```
### Algorithm
- Let `f(n)` be the number of valid sequences for `n` orders.
- **Base Case**: `f(1) = 1`.
- **Recurrence**: `f(n) = f(n-1) * n * (2n - 1)`.
- **Iterative Calculation**:
  - Initialize `ans = 1` and `MOD = 10^9 + 7`.
  - Loop with a variable `i` from 1 to `n`.
  - In each iteration, update the answer by multiplying with the ways to place the `i`-th pair. The number of ways to place the `i`-th pickup and delivery among `2i` total slots is `i * (2i - 1)`.
  - Update the answer: `ans = (ans * i * (2L * i - 1)) % MOD`.
  - After the loop, `ans` will hold the result for `f(n)`.

# Solutions
### Java

```java
class Solution {
public
  int countOrders(int n) {
    final int mod = (int)1 e9 + 7;
    long f = 1;
    for (int i = 2; i <= n; ++i) {
      f = f * i * (2 * i - 1) % mod;
    }
    return (int)f;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countOrders(int n) {
    const int mod = 1e9 + 7;
    long long f = 1;
    for (int i = 2; i <= n; ++i) {
      f = f * i * (2 * i - 1) % mod;
    }
    return f;
  }
};

```

### Python

```python
class Solution:
    def countOrders(self, n: int) -> int: mod = 10 ** 9 + 7 f = 1 for i in range(2, n + 1): f = (f * i * (2 * i - 1)) % mod return f

```