Leetcode 1259 Handshakes That Don't Cross

Problem statement

https://leetcode.com/problems/handshakes-that-dont-cross/

Solution

Let dp[n] be number of solutions for n people, than we can handshake person 0 with persons 1, 3, ... and we have the following reccurent.

dp[n] = dp[0]* dp[n-2] + dp[2]*dp[n-2-2] + ... + dp[j]*dp[n-j-2] + ...

Actually what we have here is Catalan numbers, which can be evaluated given formula $C_n = \frac{(2n)!}{n!(n+1)!}$.

Complexity

Time and space complexity is O(n), in fact we can evaluate in O(n) all Catalan numbers in range [1, n].

Code

class Solution:
    MOD, M = 10**9 + 7, 1000
    facts = [1]*(M+1)
    for i in range(1, M+1):
        facts[i] = (facts[i-1] * i) % MOD
        
    facts_inv = [1]*M + [pow(facts[M], MOD - 2, MOD)]
    for i in range(M-1, 0, -1):
        facts_inv[i] = facts_inv[i+1]*(i+1) % MOD

    def numberOfWays(self, n):
        return (self.facts[n]*self.facts_inv[n//2]*self.facts_inv[n//2+1]) % self.MOD