Count All Valid Pickup and Delivery Options

Count All Valid Pickup and Delivery Options - Problem

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 pickup(i).

Since the answer may be too large, return it modulo 10^9 + 7.

Example: If n=1, we have one order. The valid sequences are: [P1, D1]. Answer = 1.

Example: If n=2, we have two orders. Valid sequences include: [P1, P2, D1, D2], [P1, P2, D2, D1], [P1, D1, P2, D2], [P2, P1, D1, D2], [P2, P1, D2, D1], [P2, D2, P1, D1]. Answer = 6.

Input & Output

Example 1 — Single Order

$ Input: n = 1

› Output: 1

💡 Note: With 1 order, we have one pickup P1 and one delivery D1. The only valid sequence is [P1, D1], so the answer is 1.

Example 2 — Two Orders

$ Input: n = 2

› Output: 6

💡 Note: With 2 orders, valid sequences are: [P1,P2,D1,D2], [P1,P2,D2,D1], [P1,D1,P2,D2], [P2,P1,D1,D2], [P2,P1,D2,D1], [P2,D2,P1,D1]. Total = 6.

Example 3 — Three Orders

$ Input: n = 3

› Output: 90

💡 Note: With 3 orders, following the pattern: 1 × 1 × 2 × 3 × 3 × 5 = 90 valid sequences where each delivery comes after its pickup.

Constraints

1 ≤ n ≤ 500
Answer fits in 32-bit integer after taking modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Input

n orders, each with pickup Pi and delivery Di

Constraint

Every delivery Di must come after pickup Pi

Count

Total valid sequences following the constraint

Key Takeaway

🎯 Key Insight: The number of valid sequences follows the mathematical pattern ∏(i=1 to n) i × (2i-1)

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is recognizing the mathematical pattern: each new order can be inserted in 2i-1 positions, and there are i ways to assign it. The optimal approach uses the formula: result = ∏(i=1 to n) i × (2i-1). Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(n²)	O(n²)	Use recursion with memoization to count valid sequences step by step
Mathematical Formula	O(n)	O(1)	Direct calculation using combinatorial formula
Brute Force - Generate All Permutations	O((2n)!)	O(n)	Generate all possible sequences and count valid ones

Recursive with Memoization — Algorithm Steps

Define state: (unpaired_pickups, remaining_orders)
At each step, choose to place pickup (if orders remain) or delivery (if unpaired pickups exist)
Use memoization to cache results for each state

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with (0 unpaired, 2 remaining)

Make Choices

At each step: place pickup or delivery

Cache Results

Store computed results to avoid recalculation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_N 1000

long long memo[MAX_N+1][MAX_N+1];
int visited[MAX_N+1][MAX_N+1];

long long dfs(int unpaired, int remaining) {
    if (remaining == 0 && unpaired == 0) {
        return 1;
    }
    
    if (visited[unpaired][remaining]) {
        return memo[unpaired][remaining];
    }
    
    long long result = 0;
    
    // Place a pickup
    if (remaining > 0) {
        result = (result + dfs(unpaired + 1, remaining - 1)) % MOD;
    }
    
    // Place a delivery
    if (unpaired > 0) {
        result = (result + (long long)unpaired * dfs(unpaired - 1, remaining)) % MOD;
    }
    
    visited[unpaired][remaining] = 1;
    memo[unpaired][remaining] = result;
    return result;
}

int solution(int n) {
    memset(visited, 0, sizeof(visited));
    return dfs(0, n);
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each state (i,j) computed once, with i ≤ n and j ≤ n

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores results for all state combinations plus recursion stack

⚠ Quadratic Space

25.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler