Leetcode 1359: Count All Valid Pickup and Delivery Options

General Idea

Basically the idea is to iteratively count the specific “number of orders” based on the number of possible sequences for “number of orders - 1”; and the number of possibilities of placing Pickup and Delivery in each previous sequence, which can be calculated by summing up the first ((number of orders - 1) * 2 + 1) natural numbers.

The formula might be a bit vague at the first glance, let’s have a look at an example first:

Suppose we are dealing with 2 orders, and we have already known that for 1 order the answer is 1, which the only possible sequence is (P1, D1). We want to insert P2 and D2 somewhere such that D2 is always after P2, so let’s think about where we can insert P2 first.

We can insert P2 at any position in (P1, D1), and all the possibilities are: (P2, P1, D1), (P1, P2, D1) and (P1, D1, P2) with the indices being [0, 1, 2], which the number of possibilities of placing P2 is exactly k * 2 + 1, where k represents the number of orders - 1, and * 2 means each order has 2 states (Pickup and Delivery).

Why? You can think of it as we can insert P2 right after any index, plus P2 being the first before all the others, that doesn’t violate the conditions since we haven’t inserted/considered D2 yet.

Now we can imagine where to put D2 when P2 is settled down, it can be anywhere as long as after P2, right? So when P2 is at index 0, there can be 3 possibilities D2 can be placed, right after P2 at index 1 - [P2, D2, P1, D1], or after P1 - [P2, P1, D2, D1], or after D1 - [P2, P1, D1, D2]. And when P2 is at index 1, there can be 2 possibilities (D2 right after P2 - [P1, P2, D2, D1], or at the last index - [P1, P2, D1, D2]). And lastly when P2 is at index 2, the only possibility is [P1, D1, P2, D2]. Therefore, 1 * (3 + 2 + 1) = 6 in total, being the answer for 2 orders.

From the above example, we can observe the pattern: When Pickup is at index say x, The number of possibilities Delivery of the same number of orders can be placed is of (k * 2 + 1) - x, which means anywhere after x (inclusively, meaning right after Pickup). Since x can be anything in [0 .. k * 2], therefore the number of possibilities to place Pickup and Delivery, given a sequence of k (i.e., number of orders - 1), is calculated by ((k * 2 + 1) - 0, (k * 2 + 1) - 1, ... (k * 2 + 1) - k * 2). That is, for example for 3 orders, which 3 - 1 orders that has 4 states - (P1, D1, P2 and D2), the number of possibilities based on a given previous sequence is 5 + 4 + 3 + 2 + 1 = 15, that is the sum of the first (k * 2 + 1) natural numbers! And since there are 6 possible sequences for the previous number of orders (= 2), therefore for 3 orders, the answer is 6 * 15 = 90.

Overall, the answer for n orders, equals to:

(The number of possible sequences for n - 1) * (The sum of the first n natural numbers)

Code

class Solution:
    def countOrders(self, n: int) -> int:
        """
        The sum of the first n natural numbers: (n + 1) * n / 2.
        e.g. For 10: (1 + 10) + (2 + 9) + (3 + 8) + ..., in total
        that has n / 2 sets such that each set equals to n + 1.
        """
        
        ans = 1
        
        for i in range(2, n + 1):
            """
            Here i - 1 represents the previous number of orders, (* 2) represents each has 2 states Pickup and Delivery,
            that together gives the total number of elements in each of it's possible sequences. Then + 1
            represents other than placing the Pickup at the end of each element, it can be placed at the first index 
            before everyone else. Together as ((i - 1) * 2 + 1) represents the number of possible places to put the Pickup
            and hence the natural number we need.
            """
            ans = math.floor((ans * ((((i - 1) * 2 + 1) + 1) * ((i - 1) * 2 + 1) / 2)) % (10 ** 9 + 7))
        
        return ans