Handshakes That Don't Cross

How it works

The number of non-crossing handshake arrangements is exactly the n-th Catalan number, where n = numPeople/2. Catalan numbers have a closed-form formula that can be computed iteratively without solving the full recurrence.

Using the formula C(n) = C(n-1) * 2(2n-1) / (n+1), we can compute the result in linear time with constant extra space (aside from precomputing modular inverses).

Steps

1. Precompute modular multiplicative inverses for numbers 1 through n+1 using the identity inv[i] = m - (m/i) * inv[m%i] % m.
2. Initialize the Catalan number C = 1 (representing C(0)).
3. For each i from 0 to n-1:
   • Update C = C * 2 * (2i + 1) * inv[i + 2] % m.
4. Return the final value of C.

Complexity

• Time complexity: O(numPeople)

• Space complexity: O(numPeople)

Things to watch for

Forgetting to Apply Modulo at Each Step

The number of valid handshake arrangements grows exponentially and can overflow standard integer types. Applying modulo only at the end results in overflow before the modulo operation occurs. The modulo must be applied after each multiplication and addition to keep intermediate values within bounds.

Incorrect Indexing in the DP Recurrence

The recurrence dp[i] = sum(dp[j] * dp[i-j-1]) requires careful indexing. The sum runs from j = 0 to j = i-1, and the index i-j-1 must always be non-negative. Off-by-one errors in the loop bounds or index calculation lead to accessing invalid array positions or missing terms in the summation.

Not Recognizing the Catalan Number Pattern

This problem is a classic application of Catalan numbers, but many solvers try to derive the recurrence from scratch without recognizing the pattern. The key insight is that pairing person 0 with person k splits the remaining people into two independent subproblems. Understanding this structure simplifies both the implementation and debugging.

Integer Overflow in Modular Arithmetic

When computing dp[j] * dp[i-j-1], the product of two values each less than 10^9 can exceed the 32-bit integer limit. Languages like Java, C++, and Go require explicit casting to 64-bit integers before multiplication, followed by the modulo operation. Failing to use 64-bit arithmetic causes silent overflow and incorrect results.

Miscomputing Modular Inverse for the Catalan Formula

The closed-form Catalan formula requires division, which in modular arithmetic means multiplying by the modular inverse. Computing the inverse incorrectly or using the wrong formula for the inverse leads to wrong answers. The iterative inverse computation inv[i] = m - (m/i) * inv[m%i] % m must be implemented precisely with proper order of operations.

class Solution:
    def numberOfWays(self, numPeople: int) -> int:
        m = 1000000007
        n = numPeople // 2
        inv = [None] * (n+2)
        inv[1] = 1
        for i in range(2, n+2):
            k = m // i
            r = m % i
            inv[i] = m - k * inv[r] % m

        C = 1
        for i in range(n):
            C = 2 * (2 * i + 1) * inv[i + 2] * C % m

        return C

class Solution {
    const int m = 1'000'000'007;
    int mul(int a, int b) { return (long long)a * b % m; }

public:
    int numberOfWays(int numPeople) {
        int n = numPeople / 2;
        vector<int> inv(n + 2);
        inv[1] = 1;
        for (int i = 2; i < n + 2; i++) {
            int k = m / i, r = m % i;
            inv[i] = m - mul(k, inv[r]);
        }

        int C = 1;
        for (int i = 0; i < n; i++) {
            C = mul(mul(2 * (2 * i + 1), inv[i + 2]), C);
        }

        return C;
    }
};