Prerequisites
Before attempting this problem, you should be comfortable with:
- Dynamic Programming - Building solutions from smaller subproblems using recurrence relations
- Catalan Numbers - Recognizing problems that count non-crossing arrangements, which follow the Catalan sequence
- Modular Arithmetic - Applying modulo operations to prevent integer overflow and computing modular inverses for division
1. Bottom-Up Dynamic Programming
Intuition
Consider people standing in a circle. If person 0 shakes hands with person k (where k is odd, since we need an even number of people on each side), the circle splits into two independent groups: people between 0 and k, and people between k and the last person. The total ways for this configuration is the product of ways to arrange handshakes in both groups.
By summing over all valid choices for person 0's partner, we get a recurrence relation. This is precisely the Catalan number recurrence, which counts non-crossing pair arrangements.
Algorithm
- Let
dp[i]represent the number of valid handshake arrangements for2*ipeople. - Base case:
dp[0] = 1(zero people means one valid arrangement). - For each
ifrom1tonumPeople/2:- Sum over all ways to split:
dp[i] = sum(dp[j] * dp[i-j-1])forjfrom0toi-1. - Apply modulo at each step to prevent overflow.
- Sum over all ways to split:
- Return
dp[numPeople/2].
Time & Space Complexity
Time complexity:
Space complexity:
2. Top-Down Dynamic Programming (Memoization)
Intuition
The same recurrence relation can be computed recursively with memoization. Instead of building up from smaller subproblems, we start from the target and recursively compute smaller cases as needed, caching results to avoid redundant work.
This approach is often more intuitive since it directly mirrors the problem structure: to solve for n pairs, we try all ways to pair the first person and recursively solve the resulting subproblems.
Algorithm
- Create a memoization array
dpinitialized to-1, withdp[0] = 1. - Define a recursive function
calculateDP(i):- If
dp[i]is already computed, return it. - Otherwise, compute
dp[i] = sum(calculateDP(j) * calculateDP(i-j-1))forjfrom0toi-1. - Apply modulo and cache the result.
- If
- Call
calculateDP(numPeople/2)and return the result.
class Solution:
def numberOfWays(self, numPeople: int) -> int:
m = 1000000007
dp = [-1] * (numPeople // 2 + 1)
dp[0] = 1
def calculate_dp(i):
if dp[i] != -1:
return dp[i]
dp[i] = 0
for j in range(i):
dp[i] += calculate_dp(j) * calculate_dp(i - j - 1)
dp[i] %= m
return dp[i]
return calculate_dp(numPeople // 2)Time & Space Complexity
Time complexity:
Space complexity:
3. Catalan Numbers
Intuition
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).
Algorithm
- Precompute modular multiplicative inverses for numbers
1throughn+1using the identityinv[i] = m - (m/i) * inv[m%i] % m. - Initialize the Catalan number
C = 1(representingC(0)). - For each
ifrom0ton-1:- Update
C = C * 2 * (2i + 1) * inv[i + 2] % m.
- Update
- Return the final value of
C.
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 CTime & Space Complexity
Time complexity:
Space complexity:
Common Pitfalls
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.