Leetcode 1359 Count All Valid Pickup and Delivery Options

Pierre-Marie Poitevin
3 min readFeb 22, 2020

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
.

How many valid ways are there to insert P(n+1), D(n+1)? If I insert P(n+1) in the first position [0], then D(n+1) can be placed in any of the other 2n+1 positions. If P(n+1) is at position [1], then D(n+1) can be at any position after [1] in the array, or 2n different position. To generalize, if P(n+1) is at position i, D(n+1) can be placed in any of the positions i+1,…, 2n+1, or 2n+1 - i different positions. Therefore:

countOrders(n + 1) = countOrders(n) * ((2n+1) + (2n) + ... + 1)

This is an arithmetic sequence for which the sum is (2n+1) * (2n+2) / 2. Finally:

countOrders(n + 1) = countOrders(n) * (2n+1) * (2n+2) / 2

General formula

By recursion proof with countOrders(1) = 1

countOrders(n) = (2n)! / 2^ncountOrders(n + 1) = ((2n)! / 2^n) * ((2n+1 * 2n+2) / 2)…

--

--