Leetcode 1359 Count All Valid Pickup and Delivery Options

In this Leetcode problem, we are asked to count the number of valid combinations to pickup and deliver n packages so that we always pickup a package before we deliver it.

Given n orders, each order consist in pickup and delivery services.

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⁹ + 7.

Problem statement and examples

Solution

Although it is not really a computer science but a math problem, we try to resolve it by:

• Find a recursion formula
• Find a general formula if possible
• Efficiently compute the large number (use long not int!)

Recursion formula

countOrders(n + 1)
    = countOrders(n) * sum(valid P(n+1),D(n+1)) positions
    = countOrders(n) * ((2n+1) + (2n) + ... + 1)
    = countOrders(n) * (2n+1) * (2n+2) / 2

Let’s assume we know a valid combination of P1,D1,...,Pn,Dn, then any valid way we insert P(n+1) and D(n+1) in this combination will be a valid combination for P1,D1,...,P(n+1),D(n+1). Hence countOrders(n + 1)
= countOrders(n) * sum(valid P(n+1),D(n+1)) positions.