Count All Valid Pickup and Delivery Options

Hard
1060.

Count All Valid Pickup and Delivery Options

Count All Valid Pickup and Delivery Options is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Uber interviews.

There are n orders, each with a pickup and a delivery. Count the sequences of all 2n events in which every delivery comes after its own pickup.

Return the count modulo 10⁹ + 7.

Example 1

Input
n = 1
Output
1
Explanation
Only `P1, D1`.

Example 2

Input
n = 2
Output
6
Explanation
Six of the 24 orderings respect both constraints.

Example 3

Input
n = 3
Output
90

Constraints

  • 1 <= n <= 500
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countOrders = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count All Valid Pickup and Delivery Options — Solution

Count All Valid Pickup and Delivery Options solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count All Valid Pickup and Delivery Options is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Uber interviews.

Problem statement

There are n orders, each with a pickup and a delivery. Count the sequences of all 2n events in which every delivery comes after its own pickup.

Return the count modulo 10⁹ + 7.

Example 1

Input: n = 1
Output: 1
Explanation: Only `P1, D1`.

Example 2

Input: n = 2
Output: 6
Explanation: Six of the 24 orderings respect both constraints.

Example 3

Input: n = 3
Output: 90

Constraints

  • 1 <= n <= 500

Hints for Count All Valid Pickup and Delivery Options

  1. Hint 1

    Build the answer one order at a time: suppose you have a valid sequence for n - 1 orders, of length 2n - 2.

  2. Hint 2

    Inserting the new pickup has 2n - 1 slots; the delivery must then go after it.

  3. Hint 3

    Count the delivery slots and you get a clean recurrence.

How to solve Count All Valid Pickup and Delivery Options

Insert one order at a time. A valid arrangement of n-1 orders has 2n-2 events and 2n-1 gaps. Place the new pickup in any gap; that splits the sequence so the delivery has some number of legal positions after it — summing over the pickup's choices gives exactly (2n-1) · n new arrangements per old one.

Approach

  1. Start with f(0) = 1.
  2. For each i from 1 to n, set f(i) = f(i-1) · (2i - 1) · i, modulo 10⁹ + 7.
  3. Return f(n).

Why it works

The (2i-1) · i factor is the neat part. Naively, the new pair can be placed in C(2i, 2) ordered ways among 2i slots, which is i(2i-1) — and exactly half of all placements have the delivery before the pickup, so the valid count is (2i)! / (2^i) overall, matching the recurrence. Deriving it as "insert the pickup, then count legal delivery slots" is the version that generalises to related problems.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The two factors must each be reduced modulo 10⁹ + 7; their product exceeds 32 bits otherwise.
  • The answer is not (2n)! — half of every pair's orderings are invalid.
  • n = 1 gives 1, not 2.

Reference solution

Python

def countOrders(n: int) -> int:
    MOD = 10**9 + 7
    answer = 1
    for i in range(1, n + 1):
        answer = answer * (2 * i - 1) % MOD
        answer = answer * i % MOD
    return answer

Java

public static int countOrders(int n) {
    final long MOD = 1000000007L;
    long answer = 1;
    for (int i = 1; i <= n; i++) {
        answer = answer * (2L * i - 1) % MOD;
        answer = answer * i % MOD;
    }
    return (int) answer;
}

C++

int countOrders(int n) {
    const long long MOD = 1000000007LL;
    long long answer = 1;
    for (int i = 1; i <= n; i++) {
        answer = answer * (2LL * i - 1) % MOD;
        answer = answer * i % MOD;
    }
    return (int) answer;
}

JavaScript

var countOrders = function(n) {
    var MOD = 1000000007;
    var answer = 1;
    for (var i = 1; i <= n; i++) {
        answer = (answer * (2 * i - 1)) % MOD;
        answer = (answer * i) % MOD;
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming