LC-1359 Hard LeetCode

1359. Count All Valid Pickup and Delivery Options

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 65% Topics: Math, Dynamic Programming, Combinatorics

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def countOrders(self, n):
        """
        :type n: int
        :rtype: int
        """
        MOD = 10**9+7
        result = 1
        for i in reversed(xrange(2, 2*n+1, 2)):
            result = result * i*(i-1)//2 % MOD
        return result

Solution from kamyu104/LeetCode-Solutions · MIT