Skip to main content
Talentd

Count All Valid Pickup and Delivery Options - Solution & Explanation

HardMathDynamic ProgrammingCombinatorics10 min readAsked at: DoorDash, Google, Acko
Practice this problem

Problem Statement

Given n orders, each order consists of a pickup and a delivery service.

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^9 + 7.

 

Example 1:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:

Input: n = 3
Output: 90

 

Constraints:

  • 1 <= n <= 500

Approach Overview

Problem Overview: Given n pickup and delivery orders, count how many valid sequences exist such that each delivery D_i happens only after its corresponding pickup P_i. The answer grows quickly, so results are returned modulo 1e9 + 7. The challenge is counting valid permutations while respecting ordering constraints.

Approach 1: Recursive Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))

This method models the process using two variables: remaining pickups and remaining deliveries. At any step, you can place a pickup if any remain, or place a delivery if its pickup has already been used. The recursive state dp(p, d) represents the number of valid sequences with p pickups and d deliveries left. Each state branches into placing a pickup (p choices) or a valid delivery (d - p choices because those pickups are already done). Memoization stores computed states to avoid repeated work. This approach clearly shows the combinatorial structure and works well for learning recursion and dynamic programming.

Approach 2: Iterative Combinatorics Formula (Time: O(n), Space: O(1))

A mathematical observation leads to a much simpler solution. When adding the i-th order, there are 2i - 1 possible positions to insert the delivery relative to the pickup while preserving validity. The number of ways to place the pickup among current slots gives i choices, producing the recurrence f(i) = f(i-1) * i * (2i - 1). Iterating from 1 to n and multiplying these terms builds the result efficiently. This converts the counting problem into a direct formula using ideas from math and combinatorics. Only a running product and modulo operations are required.

Recommended for interviews: The combinatorics iteration is the expected optimal solution. It runs in O(n) time with constant space and shows strong pattern recognition. The recursive DP approach is still valuable during discussion because it demonstrates how to model constraints with state transitions before simplifying the counting mathematically.

Approach 1: Recursive Approach with Memoization

This approach leverages recursion with memoization to calculate the number of valid sequences. The main idea is to determine how many ways we can arrange pickups and deliveries by handling one order at a time.

This Python function uses a recursive helper function dp(p, d) that tracks how many pickups and deliveries are remaining. If both pickups and deliveries are zero, it returns 1 as a valid sequence is formed. Otherwise, it calculates the possible sequences either by picking up an order or delivering an order, avoiding violating the sequence rule.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(N^2), where N is the number of orders, due to overlapping subproblems.
Space Complexity: O(N^2) due to storing results in the memoization dictionary.

Try this approach in the editor →

Approach 2: Iterative Approach with Combinatorics

This approach uses a combinatorial method by calculating factorial operations iteratively to compute the number of valid sequences. It simplifies the problem by deriving a general formula.

This C++ solution iteratively applies a combinatorial formula that derives from possible positioning of deliveries after pickups. It computes using factorial increases corresponding to the number of current orders.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(N), where N is the number of orders.
Space Complexity: O(1), as we only maintain a constant amount of extra space.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i] as the number of all valid pickup/delivery sequences for i orders. Initially, f[1] = 1.

We can choose any of these i orders as the last delivery order D_i, then its pickup order P_i can be at any position in the previous 2 times i - 1, and the number of pickup/delivery sequences for the remaining i - 1 orders is f[i - 1], so f[i] can be expressed as:

$ f[i] = i times (2 times i - 1) times f[i - 1]

The final answer is f[n].

We notice that the value of f[i] is only related to f[i - 1], so we can use a variable instead of an array to reduce the space complexity.

The time complexity is O(n), where n is the number of orders. The space complexity is O(1)$.

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach with Memoization

Time Complexity: O(N^2), where N is the number of orders, due to overlapping subproblems.
Space Complexity: O(N^2) due to storing results in the memoization dictionary.

Iterative Approach with Combinatorics

Time Complexity: O(N), where N is the number of orders.
Space Complexity: O(1), as we only maintain a constant amount of extra space.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DP with MemoizationO(n^2)O(n^2)When explaining the state transitions or deriving the counting logic step‑by‑step
Iterative Combinatorics FormulaO(n)O(1)Optimal solution for interviews and production due to simple math formula

Video Solution

Count all Valid Pickup and Delivery Options - Leetcode 1359 - Python • NeetCodeIO • 12,331 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count All Valid Pickup and Delivery Options easy or hard?
The problem is labeled Hard because deriving the combinatorics formula is not obvious initially. Once the counting pattern is recognized, the final implementation becomes simple and runs in linear time.
Count All Valid Pickup and Delivery Options Python/Java solution
Python and Java implementations typically compute the recurrence f(i) = f(i-1) * i * (2i - 1) using a loop from 1 to n while applying modulo 1e9+7. The code uses integer arithmetic and a single accumulator variable, making the implementation concise and efficient.
How to solve Count All Valid Pickup and Delivery Options in O(n)?
Observe that when adding the i-th order, there are i possible positions for the pickup and (2i−1) valid positions for its delivery relative to other events. Multiply the previous result by i * (2i − 1) for each i from 1 to n. Apply modulo 1e9+7 after every multiplication.
What is the best approach for Count All Valid Pickup and Delivery Options?
The optimal approach uses a combinatorics formula derived from counting valid insertion positions for each new order. The recurrence is f(i) = f(i-1) * i * (2i - 1). Iterating from 1 to n computes the result in O(n) time and O(1) space with modulo 1e9+7.
Is Count All Valid Pickup and Delivery Options asked at Google/Amazon/Meta?
Combinatorics and dynamic programming counting problems like this appear in interviews at companies such as Amazon, Google, and Meta. Interviewers use them to test mathematical reasoning, recurrence derivation, and the ability to optimize DP into a formula.
What data structure is used in Count All Valid Pickup and Delivery Options?
The recursive approach uses memoization with a 2D DP table keyed by remaining pickups and deliveries. The optimal solution does not require a data structure; it relies on combinatorial counting and a running product with modular arithmetic.
What is the time complexity of Count All Valid Pickup and Delivery Options?
The optimal combinatorics solution runs in O(n) time and O(1) space because it only multiplies a running product for each order. A recursive dynamic programming formulation with memoization typically requires O(n^2) time and space due to the number of pickup/delivery states.

Ready to solve this problem?

Practice Count All Valid Pickup and Delivery Options with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer