1359. Pickup Deliveries

Count All Valid Pickup and Delivery Options

Another wonderful bottom up DP training.

A bit simpler than problem 552.

At least that's how I feel.

Base Case

With only one order, there's only one valid arrangement: pickup first (P), then delivery (D), giving a count of 1.

It looks like this: $(P_1, D_1)$.

Observing the Path Upward 🧗

1. How to Place $P_2$ and $D_2$

$P_i$ must always appear to the left of $D_i$. This is our problem's requirement.

So let's first figure out where $P_2$ can go.

The sequence $(P_1, D_1)$ has 3 slots where $P_2$ can insert itself.

Once $P_2$ is placed, 4 slots are formed. However, at $P_2$'s perspective, they vary:

I. Place before $P_1$: 1 + 3 format

Left side of $+$: slots to the left of $P_2$

Right side of $+$: slots to the right of $P_2$

II. Place between $P_1$ and $D_1$: 2 + 2 format

III. Place after $D_1$: 3 + 1 format

Since $P_i$ must always be to the left of $D_i$, once $P_2$ is placed, $D_2$ can only go into slots to the right, which are those on the right of $+$.

Total valid slots for $D_2$: $1 + 2 + 3 = 6$.

So with 2 orders, our count is $1 \times 6 = 6$.

2. Generalizing to $P_j$ and $D_j$ for $2 \leq j$

When $P_j$ and $D_j$ are about to be inserted, there are already $j - 1$ orders in front,

forming a sequence of length $2j - 2$, from which $P_j$ thus has $2j - 1$ slots to choose.

From left to right, number of valid slots available to $D_j$ after placing $P_j$ is $2j - 1, \ldots, 1$ respectively.

This is an arithmetic series summing to $j(2j - 1)$, the exact multiplier applied to previous count $C_{j-1}$ when arranging $P_j$ and $D_j$.

Thereby, our state transition equation is:

$C_j = C_{j - 1} \times j(2j - 1) \quad \forall \; j \in \mathbb{N}; \; 2 \leq j$

Time to write the code 🧑🏻‍💻👩🏻‍💻

As always, numbers can get astronomically large. Don't forget to apply modulo.

C++

#include <cmath>
using namespace std;

int countValidSequences(int totalOrders) // LeetCode Q.1359.
{
    long long modulo = pow(10, 9) + 7; // Long long prevents overflow.

    // Base case when n is 1: pickup 1 followed by delivery 1.
    long long validSequences = 1;

    for (int prevOrderNum = 1; prevOrderNum <= totalOrders - 1; prevOrderNum++) {
        int spotsCount = 2 * prevOrderNum + 1;

        // Sum from 1 to spots count.
        int multiple = spotsCount * (spotsCount + 1) / 2;

        validSequences *= multiple;
        validSequences %= modulo;
    }

    return validSequences;
}

Python

def count_valid_sequences(total_orders: int) -> int:  # LeetCode Q.1359.
    modulo = 10 ** 9 + 7

    # Base case when n is 1: pickup 1 followed by delivery 1.
    valid_sequences = 1

    for prev_order_num in range(1, total_orders):
        spots_count = 2 * prev_order_num + 1

        # Sum from 1 to spots count.
        multiple = spots_count * (spots_count + 1) // 2

        valid_sequences *= multiple
        valid_sequences %= modulo

    return valid_sequences

$O(n)$ time, $O(1)$ space. Be sure to practice writing the transition equation by hand too.