1359. Count all Valid Pickup and Delivery Options - Explanation

1. Recursion

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007

        def dfs(picked, delivered):
            if picked == n and delivered == n:
                return 1

            res = 0
            if picked < n:
                res = (res + (n - picked) * dfs(picked + 1, delivered)) % MOD
            if delivered < picked:
                res = (res + (picked - delivered) * dfs(picked, delivered + 1)) % MOD

            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        dp = [[-1] * (n + 1) for _ in range(n + 1)]
        dp[n][n] = 1

        def dfs(picked, delivered):
            if dp[picked][delivered] != -1:
                return dp[picked][delivered]

            res = 0
            if picked < n:
                res = (res + (n - picked) * dfs(picked + 1, delivered)) % MOD
            if delivered < picked:
                res = (res + (picked - delivered) * dfs(picked, delivered + 1)) % MOD

            dp[picked][delivered] = res
            return res

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for picked in range(n + 1):
            for delivered in range(n + 1):
                if picked < n:
                    dp[picked + 1][delivered] = (
                        (dp[picked + 1][delivered] +
                        (n - picked) * dp[picked][delivered]) % MOD
                    )

                if delivered < picked:
                    dp[picked][delivered + 1] = (
                        (dp[picked][delivered + 1] +
                        (picked - delivered) * dp[picked][delivered]) % MOD
                    )

        return dp[n][n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized)

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        dp = [0] * (n + 1)
        dp[0] = 1

        for picked in range(n + 1):
            for delivered in range(picked):
                dp[delivered + 1] = (
                    (dp[delivered + 1] +
                    (picked - delivered) * dp[delivered]) % MOD
                )

            if picked < n:
                next_dp = [0] * (n + 1)
                for delivered in range(picked + 1):
                    next_dp[delivered] = (
                        (next_dp[delivered] +
                        (n - picked) * dp[delivered]) % MOD
                    )
                dp = next_dp

        return dp[n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

5. Combinatorics

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        slots, res = 2 * n, 1
        while slots > 0:
            valid_choices = slots * (slots - 1) // 2
            res = (res * valid_choices) % MOD
            slots -= 2
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

6. Probability

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        res = 1

        for slot in range(1, 2 * n + 1):
            res  *= slot
            if slot % 2 == 0:
                res >>= 1
            res %= MOD

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$