Leetcode 1359. Count All Valid Pickup and Delivery Options

Problem Explanation

The problem requires us to count all possible sequences of pick-up and delivery orders where each delivery should occur after its respective pick-up order. For n orders, each order consists of one pick-up(P) and one delivery(D) service. Hence, the total positions will be 2*n.

Let's consider an example to understand better:

Suppose, n = 3. It means there are 3 pick-up orders (P1,P2,P3) and 3 respective delivery orders (D1, D2, D3). There could be possible sequences like (P1,D1,P2,D2,P3,D3) or (P1,P2,P3,D1,D2,D3) etc. But remember, it has to always maintain one condition: delivery of an order must occur after the pick-up of that order; that's why (P1,D2,P2,D1,P3,D3) is not a valid sequence as D1 occurred after P2.

Solution Approach

We can solve this problem using the concept of permutations and combinations. The solution approach can be summed up into the following steps:

  • For order i, we can choose any position from [2 * (i -1) + 1, 2 * i] for Pi
  • For order i, we can choose any position from [2 * i, 2 * i + 1] for Di

The count of valid possibilities for each order is calculated as i * (2 * i - 1), which is then multiplied with the answer we get for the previous orders. Since the answer can be huge, we should take modulo at each step to prevent overflow.

Solution

Python

1
2python
3class Solution:
4    def countOrders(self, n: int) -> int:
5        MOD = 10 ** 9 + 7
6        ans = 1
7        for i in range(1, n + 1):
8            ans *= i * (2 * i - 1)
9            ans %= MOD
10        return ans

Java

1
2java
3class Solution {
4    public int countOrders(int n) {
5        int MOD = 1000000007;
6        long ans = 1;
7        for (int i = 1; i <= n; i++)
8            ans = (ans * i % MOD) * (2 * i - 1) % MOD;
9        return (int)ans;
10    }
11}

Javascript

1
2javascript
3var countOrders = function(n) {
4    let MOD = 1000000007;
5    let ans = 1;
6    for (let i = 1; i <= n; i++)
7        ans = (ans * i % MOD) * (2 * i - 1) % MOD;
8    return ans
9};

C++

1
2cpp
3class Solution {
4public:
5    int countOrders(int n) {
6        int MOD = 1000000007;
7        long ans = 1;
8        for (int i = 1; i <= n;  i++)
9            ans = (ans * i % MOD) * (2 * i - 1) % MOD;
10        return ans;
11    }
12};

C#

1
2csharp
3public class Solution {
4    public int CountOrders(int n) {
5        int MOD = 1000000007;
6        long ans = 1;
7        for (int i = 1; i <= n;  i++)
8            ans = (ans * i % MOD) * (2 * i - 1) % MOD;
9        return (int)ans;
10    }
11}

Conclusion

In this problem, we have learned about how we can use the concept of permutations and combinations to find all valid sequences for a set of pickup and delivery orders. The key in the solution approach is to determine the number of valid possibilities for each order and to multiply this count with the answer for the previous orders.

It is also important to remember to take modulo at each step to prevent overflow since the answer can be very large.

The problem has been comprehensively solved with solutions provided in Python, Java, Javascript, C++, and C# programming languages. However, it is important to note that the approach remains the same for all languages, the key difference being the language syntax and some language-specific features.

Understanding this problem can be helpful in a range of applications like order management in restaurants, cab service management where the pickup and drop of a passenger from one location to another location should be maintained in order, etc.

Through problem-solving like this, we can enhance our logical thinking and coding skills. So, keep practicing more and more challenging problems. Happy coding!


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫