Problem Description

The "Handshakes That Don't Cross" problem asks you to determine how many valid ways people can shake hands around a round table such that no two handshakes cross each other.

Specifically, given n people (where n is always even), each person must shake hands with exactly one other person. A handshake is represented by a straight line drawn between two people sitting around the table. Handshakes are considered non-crossing if no two handshake lines intersect inside the circle.

Your goal is, for a given even n, to return the number of ways such non-crossing handshakes can be made.

Constraints:

• n is even and in the range 0 ≤ n ≤ 1000
• Each person shakes hands with exactly one other person
• No two handshakes cross

Thought Process

Let's break down the problem conceptually:

• If we try to pair up people naively, we quickly run into the issue of handshakes crossing, so brute-forcing all possible pairings and checking for crossings is inefficient.
• We notice that if we fix one person and pair them with another, this divides the circle into two smaller groups. The handshakes within each group must also be non-crossing.
• This recursive structure hints at a dynamic programming approach, where the solution for n people can be built from solutions to smaller subproblems.
• Upon research or by recognizing the pattern, this is a classic Catalan Numbers problem, where the n/2-th Catalan number gives the answer for n people.

Solution Approach

Let's outline the algorithm step-by-step:

1. Recognize the Subproblem: For n people, we want the number of non-crossing handshake pairings. For n = 0, there is 1 way (no handshakes).
2. Recursive Structure:
   • Fix person 1, and pair them with person k (where k is even and between 2 and n).
   • This splits the circle into two groups: one with k-2 people (between person 2 and person k-1), and one with n-k people (the rest).
   • The total ways is the sum over all possible k of the product of the number of ways to handshake in each group.
3. Dynamic Programming:
   • Let dp[i] denote the number of valid handshake pairings for i people.
   • Base case: dp[0] = 1 (no people, one way).
   • For even i: dp[i] = sum(dp[j] * dp[i-2-j]) for all even j from 0 to i-2.
4. Implementation:
   • Iteratively fill the dp array up to n.
   • Return dp[n] as the answer.

Example Walkthrough

Let's walk through an example with n = 4:

• People: 1, 2, 3, 4 sitting around a table.
• We want to pair everyone such that handshakes don't cross.

• Fix person 1. They can shake hands with:
  • Person 2: Splits into groups of 0 (empty) and 2 (people 3 and 4). Ways: 1 * 1 = 1.
  • Person 4: Splits into groups of 2 (people 2 and 3) and 0 (empty). Ways: 1 * 1 = 1.
• Total ways: 1 + 1 = 2.
• The two non-crossing configurations are:
  • (1-2, 3-4)
  • (1-4, 2-3)

Time and Space Complexity

Brute-force Approach:

• Enumerate all possible pairings and check if any two handshakes cross.
• The number of pairings grows super-exponentially, making this infeasible for large n.
• Time complexity: Worse than exponential (factorial in nature).

• We use a DP array of size n+1.
• For each even i up to n, we sum over roughly i/2 terms.
• Total time complexity: O(n^2).
• Space complexity: O(n) for the DP array.

Summary

The "Handshakes That Don't Cross" problem is a classic example of recursive combinatorics and dynamic programming. The key insight is recognizing that the problem is equivalent to computing Catalan numbers, which count the number of valid non-crossing pairings. By breaking the problem into subproblems and using a DP array, we can efficiently compute the answer for large n. This approach is elegant because it leverages mathematical properties and avoids brute-force enumeration.

Code Implementation

class Solution:
    def numberOfWays(self, num_people: int) -> int:
        MOD = 10**9 + 7
        n = num_people
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(2, n + 1, 2):
            for j in range(0, i, 2):
                dp[i] = (dp[i] + dp[j] * dp[i - 2 - j]) % MOD
        return dp[n]
      

class Solution {
public:
    int numberOfWays(int num_people) {
        const int MOD = 1e9 + 7;
        int n = num_people;
        std::vector dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 2; i <= n; i += 2) {
            for (int j = 0; j <= i - 2; j += 2) {
                dp[i] = (dp[i] + dp[j] * dp[i - 2 - j]) % MOD;
            }
        }
        return (int)dp[n];
    }
};
      

class Solution {
    public int numberOfWays(int num_people) {
        int MOD = 1000000007;
        int n = num_people;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 2; i <= n; i += 2) {
            for (int j = 0; j <= i - 2; j += 2) {
                dp[i] = (dp[i] + dp[j] * dp[i - 2 - j]) % MOD;
            }
        }
        return (int)dp[n];
    }
}
      

var numberOfWays = function(num_people) {
    const MOD = 1e9 + 7;
    let n = num_people;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 2; i <= n; i += 2) {
        for (let j = 0; j <= i - 2; j += 2) {
            dp[i] = (dp[i] + dp[j] * dp[i - 2 - j]) % MOD;
        }
    }
    return dp[n];
};