Problem

You are given an even number of people numPeople that stand around a circle and each person shakes hands with someone else so that there are numPeople / 2 handshakes total.

Return the number of ways these handshakes could occur such that none of the handshakes cross.

Since the answer could be very large, return it modulo 109 + 7.

Examples

Example 1:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1200-1299/1259.Handshakes%20That%20Don%27t%20Cross/images/5125_example_2.png)
Input: numPeople = 4
Output: 2
Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].

Example 2:

1
2
3

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1200-1299/1259.Handshakes%20That%20Don%27t%20Cross/images/5125_example_3.png)
Input: numPeople = 6
Output: 5

Constraints:

  • 2 <= numPeople <= 1000
  • numPeople is even.

Solution

Method 1 – Dynamic Programming (Catalan Numbers)

Intuition

The problem asks for the number of ways to pair up people in a circle such that no handshakes cross. This is a classic application of the Catalan numbers, which count the number of non-crossing handshakes (or valid parenthesis sequences, binary trees, etc.).

Approach

  1. Let n = numPeople / 2. The answer is the nth Catalan number.
  2. Use dynamic programming to compute Catalan numbers:
    • dp[0] = 1 (base case: 0 pairs)
    • For each i from 1 to n, compute dp[i] = sum_{j=0}^{i-1} dp[j] * dp[i-1-j].
    • Take modulo 10^9 + 7 at each step.
  3. Return dp[n] as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int numberOfWays(int numPeople) {
        int n = numPeople / 2, mod = 1e9 + 7;
        vector<long long> dp(n+1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % mod;
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func numberOfWays(numPeople int) int {
    n, mod := numPeople/2, int(1e9+7)
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            dp[i] = (dp[i] + dp[j]*dp[i-1-j]) % mod
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int numberOfWays(int numPeople) {
        int n = numPeople / 2, mod = 1_000_000_007;
        long[] dp = new long[n+1];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % mod;
            }
        }
        return (int)dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun numberOfWays(numPeople: Int): Int {
        val n = numPeople / 2
        val mod = 1_000_000_007
        val dp = LongArray(n+1)
        dp[0] = 1L
        for (i in 1..n) {
            for (j in 0 until i) {
                dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % mod
            }
        }
        return dp[n].toInt()
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def numberOfWays(self, numPeople: int) -> int:
        n, mod = numPeople // 2, 10**9 + 7
        dp: list[int] = [0] * (n+1)
        dp[0] = 1
        for i in range(1, n+1):
            for j in range(i):
                dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % mod
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct Solution;
impl Solution {
    pub fn number_of_ways(num_people: i32) -> i32 {
        let n = (num_people / 2) as usize;
        let m = 1_000_000_007;
        let mut dp = vec![0i64; n+1];
        dp[0] = 1;
        for i in 1..=n {
            for j in 0..i {
                dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % m;
            }
        }
        dp[n] as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    numberOfWays(numPeople: number): number {
        const n = numPeople / 2, mod = 1e9 + 7;
        const dp: number[] = Array(n+1).fill(0);
        dp[0] = 1;
        for (let i = 1; i <= n; ++i) {
            for (let j = 0; j < i; ++j) {
                dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % mod;
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), since for each i up to n, we sum over all j < i.
  • 🧺 Space complexity: O(n), for the dp array.