1359. Count all Valid Pickup and Delivery Options - Explanation

1. Recursion

Intuition

We need to count all valid orderings where each delivery happens after its corresponding pickup. At any point, we can either pick up a new order (if any remain) or deliver an order that has already been picked up. The number of choices at each step depends on how many orders are still available for pickup and how many are picked but not yet delivered.

Algorithm

Use recursion with two state variables: the count of picked orders and delivered orders.
At each step, if we can pick up more orders, branch with (n - picked) choices for which order to pick next.
If there are orders picked but not delivered, branch with (picked - delivered) choices for which order to deliver.
Return 1 when all orders are picked and delivered (base case).
Multiply the count of choices at each branch and sum all paths.

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007

        def dfs(picked, delivered):
            if picked == n and delivered == n:
                return 1

            res = 0
            if picked < n:
                res = (res + (n - picked) * dfs(picked + 1, delivered)) % MOD
            if delivered < picked:
                res = (res + (picked - delivered) * dfs(picked, delivered + 1)) % MOD

            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recalculates the same states multiple times. For example, the state (picked=2, delivered=1) might be reached through different orderings. By caching these results, we avoid redundant computation.

Algorithm

Create a 2D memoization table indexed by (picked, delivered).
Before computing a state, check if it exists in the cache and return it if found.
Apply the same recursive logic as before: pick an unpicked order or deliver a picked order.
Store the computed result in the cache before returning.
Start the recursion from (0, 0) and return the cached result.

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        dp = [[-1] * (n + 1) for _ in range(n + 1)]
        dp[n][n] = 1

        def dfs(picked, delivered):
            if dp[picked][delivered] != -1:
                return dp[picked][delivered]

            res = 0
            if picked < n:
                res = (res + (n - picked) * dfs(picked + 1, delivered)) % MOD
            if delivered < picked:
                res = (res + (picked - delivered) * dfs(picked, delivered + 1)) % MOD

            dp[picked][delivered] = res
            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursing from (0, 0) and memoizing, we can build the solution iteratively. We start from the base case where no orders are processed and accumulate the number of ways to reach each state by considering all valid transitions.

Algorithm

Create a 2D DP table where dp[picked][delivered] represents the number of ways to reach that state.
Initialize dp[0][0] = 1 as the starting point.
Iterate through all states in order of increasing picked and delivered counts.
For each state, add its contribution to the next states: picking a new order or delivering a picked order.
Return dp[n][n] as the final answer.

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for picked in range(n + 1):
            for delivered in range(n + 1):
                if picked < n:
                    dp[picked + 1][delivered] = (
                        (dp[picked + 1][delivered] +
                        (n - picked) * dp[picked][delivered]) % MOD
                    )

                if delivered < picked:
                    dp[picked][delivered + 1] = (
                        (dp[picked][delivered + 1] +
                        (picked - delivered) * dp[picked][delivered]) % MOD
                    )

        return dp[n][n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized)

Intuition

In the bottom-up approach, when processing states for a given number of picked orders, we only need the current row of delivered counts. After processing all deliveries for the current picked count, we can transition to the next picked count and discard the old row.

Algorithm

Use a 1D array dp to track the number of ways for each delivered count.
For each picked count, first process all possible deliveries within that row.
Before moving to the next picked count, create a new array and populate it based on the pickup transition.
Continue until all n orders are processed.
Return dp[n] which represents the state where all n orders are picked and delivered.

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        dp = [0] * (n + 1)
        dp[0] = 1

        for picked in range(n + 1):
            for delivered in range(picked):
                dp[delivered + 1] = (
                    (dp[delivered + 1] +
                    (picked - delivered) * dp[delivered]) % MOD
                )

            if picked < n:
                next_dp = [0] * (n + 1)
                for delivered in range(picked + 1):
                    next_dp[delivered] = (
                        (next_dp[delivered] +
                        (n - picked) * dp[delivered]) % MOD
                    )
                dp = next_dp

        return dp[n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

5. Combinatorics

Intuition

Think of placing pickup and delivery events into 2n slots. For each order, we place its pickup first and then choose where to put the delivery among the remaining slots. When placing order i, there are (2i - 1) slots left, and we can place the delivery in any of the (2i - 1) * 2i / 2 ways (choosing 2 slots for the pair where pickup comes first).

Algorithm

Initialize the result to 1 and start with 2n available slots.
For each order, compute the number of valid ways to place its pickup-delivery pair: slots * (slots - 1) / 2.
Multiply this into the result and reduce the slot count by 2.
Repeat until all orders are placed.
Return the result modulo 10^9 + 7.

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        slots, res = 2 * n, 1
        while slots > 0:
            valid_choices = slots * (slots - 1) // 2
            res = (res * valid_choices) % MOD
            slots -= 2
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

6. Probability

Intuition

The total number of arrangements of 2n events is (2n)!. However, for each order, the delivery must come after the pickup, which has a 1/2 probability in a random arrangement. Since we have n independent orders, the valid arrangements are (2n)! / 2^n.

Algorithm

Initialize the result to 1.
Iterate through slots from 1 to 2n.
Multiply the result by the current slot number.
Whenever the slot is even (meaning we just placed a delivery), divide by 2 to account for the ordering constraint.
Take modulo at each step and return the final result.

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        res = 1

        for slot in range(1, 2 * n + 1):
            res  *= slot
            if slot % 2 == 0:
                res >>= 1
            res %= MOD

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting Modular Arithmetic

The result grows extremely fast (factorial-like), causing integer overflow. You must take modulo at each multiplication step, not just at the end.

# Wrong: overflow before final mod
res = res * validChoices
return res % MOD

# Correct: mod at each step
res = (res * validChoices) % MOD

Allowing Delivery Before Pickup

Some solutions incorrectly count all permutations of 2n events. The constraint that each delivery must come after its pickup is essential and reduces valid arrangements by a factor of 2^n.

Integer Overflow in Intermediate Calculations

When multiplying two integers before taking modulo, the intermediate result can overflow. Use explicit casting to long or 64-bit integers.

// Wrong: overflow before mod
res = (res + (n - picked) * dfs(...)) % MOD;

// Correct: cast to long first
res = (res + (n - picked) * 1L * dfs(...)) % MOD;

Miscounting Slot Choices

In the combinatorics approach, the valid choices for placing a pickup-delivery pair is slots * (slots - 1) / 2, not slots * (slots - 1). The division by 2 accounts for the fact that pickup must come before delivery.

Wrong Base Case in Recursion

The base case should return 1 when all orders are picked AND delivered, not just when all are picked. Returning early causes undercounting.