1359. Count All Valid Pickup and Delivery Options

Problem Description

Given n orders, each consisting of a pickup and a delivery, count all valid pickup/delivery sequences where delivery(i) always comes after pickup(i). Return the count modulo 109 + 7.

Solution: Dynamic Programming

This problem can be efficiently solved using dynamic programming. Let's define f[i] as the number of valid pickup/delivery sequences for i orders.

Base Case: For i = 1, there's only one valid sequence (P1, D1), so f[1] = 1.

Recursive Relation: For i orders, consider the last delivery, Di. Its corresponding pickup, Pi, must come before it. There are 2i - 1 possible positions for Pi among the already placed 2i - 2 elements. Then, there are i choices for which delivery will be the last one. The remaining i-1 orders can be arranged in f[i-1] ways. Therefore:

f[i] = i * (2i - 1) * f[i-1]

We can iteratively calculate f[i] for i from 2 to n, accumulating the result modulo 109 + 7 to handle potential overflow.

Time and Space Complexity

• Time Complexity: O(n) - We iterate through the numbers from 1 to n.
• Space Complexity: O(1) - We use a constant amount of extra space to store the intermediate result. (We could use an array f, but this is unnecessary; we only need the previous result to calculate the current one).

Code Implementation (Python)

class Solution:
    def countOrders(self, n: int) -> int:
        mod = 10**9 + 7
        f = 1
        for i in range(2, n + 1):
            f = (f * i * (2 * i - 1)) % mod
        return f
 

Code Implementation (Java)

class Solution {
    public int countOrders(int n) {
        long mod = (long)1e9 + 7;
        long f = 1;
        for (int i = 2; i <= n; ++i) {
            f = (f * i * (2 * i - 1)) % mod;
        }
        return (int) f;
    }
}

Code Implementation (C++)

class Solution {
public:
    int countOrders(int n) {
        long long mod = 1e9 + 7;
        long long f = 1;
        for (int i = 2; i <= n; ++i) {
            f = (f * i * (2 * i - 1)) % mod;
        }
        return f;
    }
};

Code Implementation (Go)

func countOrders(n int) int {
	mod := int64(1e9 + 7)
	f := int64(1)
	for i := 2; i <= n; i++ {
		f = f * int64(i) * int64(2*i-1) % mod
	}
	return int(f)
}

Code Implementation (Rust)

const MOD: i64 = 1_000_000_007;
 
impl Solution {
    pub fn count_orders(n: i32) -> i32 {
        let mut f: i64 = 1;
        for i in 2..=n as i64 {
            f = (f * i * (2 * i - 1)) % MOD;
        }
        f as i32
    }
}

All the code implementations follow the same dynamic programming approach. The key is the iterative calculation of f[i] using the recursive relation and modulo operation to prevent integer overflow.