Watch 3 video solutions for Handshakes That Don't Cross, a hard level problem involving Math, Dynamic Programming. This walkthrough by Kelvin Chandra has 2,757 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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:
Input: numPeople = 6 Output: 5
Constraints:
2 <= numPeople <= 1000numPeople is even.Problem Overview: Given an even number n representing people standing in a circle, each person must shake hands with exactly one other person. Handshakes cannot cross. The task is to count how many valid pairing arrangements exist.
Approach 1: Brute Force Recursive Pairing (Exponential)
The most direct idea tries every possible handshake choice for the first person. Pair person 0 with any other valid partner 2k+1, which splits the circle into two independent subproblems. Recursively count valid pairings inside the left and right partitions and multiply them. This naturally models the non‑crossing constraint because once a pair is chosen, everything inside and outside that arc must remain independent. The recursion recomputes the same states many times, leading to exponential time complexity O(2^n) with recursion depth O(n).
Approach 2: Memoization Search (Catalan DP) (Time: O(n^2), Space: O(n))
The recursive structure reveals a classic Catalan number recurrence. Let dp[i] represent the number of valid ways to form non‑crossing handshakes among 2 * i people. If the first person pairs with person 2k+1, the people inside that arc form k pairs and the outside group forms i-1-k pairs. The recurrence becomes dp[i] = sum(dp[k] * dp[i-1-k]). A top‑down dynamic programming solution with memoization caches each dp[i], eliminating repeated computation. Since each state iterates over at most i splits, the total runtime becomes O(n^2) and space O(n). Results are typically computed modulo 1e9+7.
Approach 3: Bottom-Up Dynamic Programming (Time: O(n^2), Space: O(n))
The same recurrence can be implemented iteratively. Initialize dp[0] = 1, then compute values for increasing numbers of pairs. For each i, iterate k from 0 to i-1 and accumulate dp[k] * dp[i-1-k]. This avoids recursion overhead and keeps the logic straightforward. The approach still performs roughly n^2/2 multiplications but is easy to reason about and commonly used when solving Catalan problems in math and dynamic programming.
Approach 4: Catalan Number Formula (Time: O(n), Space: O(n))
The sequence of valid handshake counts is exactly the Catalan sequence. For i pairs, the value equals C_i = (2i)! / ((i+1)! * i!). With precomputed factorials and modular inverses, the result can be calculated in linear time. This approach is mathematically elegant and faster asymptotically, but interviewers usually expect candidates to derive the DP recurrence before jumping to the closed form.
Recommended for interviews: Use the memoized or bottom‑up Catalan DP. It clearly shows you understand the non‑crossing partition insight and the recurrence structure. Mentioning the Catalan number connection strengthens the explanation and demonstrates deeper algorithmic knowledge.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursive Pairing | O(2^n) | O(n) | Conceptual starting point to understand how non-crossing splits the circle into subproblems |
| Memoization Search (Top-Down DP) | O(n^2) | O(n) | Best practical solution when implementing recursion with cached subproblems |
| Bottom-Up Dynamic Programming | O(n^2) | O(n) | Iterative DP preferred when avoiding recursion or stack overhead |
| Catalan Number Formula | O(n) | O(n) | When factorials and modular inverses are precomputed for fast combinatorial calculation |