Handshakes That Don't Cross solution and explanation
4 more videos on this problem
1259 Handshakes That Don't Cross (Biweekly Contest 13)Kelvin Chandra · 6:08 · 2K views
1259. Handshakes That Don't Cross - Week 4/4 Leetcode February ChallengeProgramming Live with Larry · 15:46 · 412 views
1259. Handshakes That Don't Cross - Week 3/5 Leetcode June ChallengeProgramming Live with Larry · 13:22 · 172 views
Handshakes That Don't Cross - Leetcode 1259 - Java - Dynamic ProgrammingData Structures and Algorithms · 21:25 · 37 views
LeetCode 1259: Handshakes That Don't CrossAlitaCode · 28:25 · 9 views
The 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.
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 <= 1000numPeopleis even.
Approach overview
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.
Solution
We design a function dfs(i), which represents the number of handshake schemes for i people. The answer is dfs(n).
The execution logic of the function dfs(i) is as follows:
- If
i \lt 2, then there is only one handshake scheme, which is not to shake hands, so return1. - Otherwise, we can enumerate who the first person shakes hands with. Let the number of remaining people on the left be
l, and the number of people on the right ber=i-l-2. Then we havedfs(i)= sum_{l=0}^{i-1} dfs(l) times dfs(r).
To avoid repeated calculations, we use the method of memoization search.
The time complexity is O(n^2), and the space complexity is O(n). Where n is the size of numPeople.
class Solution:
def numberOfWays(self, numPeople: int) -> int:
@cache
def dfs(i: int) -> int:
if i < 2:
return 1
ans = 0
for l in range(0, i, 2):
r = i - l - 2
ans += dfs(l) * dfs(r)
ans %= mod
return ans
mod = 10**9 + 7
return dfs(numPeople)class Solution {
private int[] f;
private final int mod = (int) 1e9 + 7;
public int numberOfWays(int numPeople) {
f = new int[numPeople + 1];
return dfs(numPeople);
}
private int dfs(int i) {
if (i < 2) {
return 1;
}
if (f[i] != 0) {
return f[i];
}
for (int l = 0; l < i; l += 2) {
int r = i - l - 2;
f[i] = (int) ((f[i] + (1L * dfs(l) * dfs(r) % mod)) % mod);
}
return f[i];
}
}class Solution {
public:
int numberOfWays(int numPeople) {
const int mod = 1e9 + 7;
int f[numPeople + 1];
memset(f, 0, sizeof(f));
function<int(int)> dfs = [&](int i) {
if (i < 2) {
return 1;
}
if (f[i]) {
return f[i];
}
for (int l = 0; l < i; l += 2) {
int r = i - l - 2;
f[i] = (f[i] + 1LL * dfs(l) * dfs(r) % mod) % mod;
}
return f[i];
};
return dfs(numPeople);
}
};function numberOfWays(numPeople: number): number {
const mod = 10 ** 9 + 7;
const f: number[] = Array(numPeople + 1).fill(0);
const dfs = (i: number): number => {
if (i < 2) {
return 1;
}
if (f[i] !== 0) {
return f[i];
}
for (let l = 0; l < i; l += 2) {
const r = i - l - 2;
f[i] += Number((BigInt(dfs(l)) * BigInt(dfs(r))) % BigInt(mod));
f[i] %= mod;
}
return f[i];
};
return dfs(numPeople);
}func numberOfWays(numPeople int) int {
const mod int = 1e9 + 7
f := make([]int, numPeople+1)
var dfs func(int) int
dfs = func(i int) int {
if i < 2 {
return 1
}
if f[i] != 0 {
return f[i]
}
for l := 0; l < i; l += 2 {
r := i - l - 2
f[i] = (f[i] + dfs(l)*dfs(r)) % mod
}
return f[i]
}
return dfs(numPeople)
}Complexity analysis
| 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 |
Frequently asked questions
Is Handshakes That Don't Cross easy or hard?
The problem is labeled Hard because recognizing the Catalan recurrence is not obvious at first. Once the connection to Catalan numbers or non‑crossing partitions is identified, the implementation becomes a straightforward O(n^2) dynamic programming solution.
Handshakes That Don't Cross Python/Java solution
The typical implementation uses memoized recursion or bottom‑up DP with a modulo of 1e9+7. Python, Java, C++, Go, and TypeScript versions all follow the same recurrence dp[i] = sum(dp[k] * dp[i-1-k]) while iterating over valid split points.
How to solve Handshakes That Don't Cross in O(n)?
Using the mathematical Catalan number formula. The number of valid handshake arrangements for n people equals Catalan(n/2). With precomputed factorials and modular inverses, the value Cn = (2n)! / ((n+1)! * n!) can be evaluated in O(n) preprocessing time and O(1) per query.
What is the best approach for Handshakes That Don't Cross?
The standard solution uses dynamic programming based on the Catalan number recurrence. Let dp[i] represent the number of ways to arrange non‑crossing handshakes among 2*i people. Each pairing splits the circle into two independent groups, producing the recurrence dp[i] = sum(dp[k] * dp[i-1-k]). This runs in O(n^2) time and O(n) space.
Is Handshakes That Don't Cross asked at Google/Amazon/Meta?
Variations of Catalan number problems appear in interviews at companies like Google, Amazon, and Meta. The structure is similar to problems such as counting valid parentheses or non‑crossing chords in a circle, which test dynamic programming and combinatorics understanding.
What data structure is used in Handshakes That Don't Cross?
The core structure is a dynamic programming array or memoization cache storing the number of ways to form valid pairings for a given number of pairs. Each entry represents a Catalan number computed from smaller subproblems.
What is the time complexity of Handshakes That Don't Cross?
The dynamic programming solution runs in O(n^2) time where n/2 represents the number of handshake pairs. For each DP state you iterate through all possible split points. Space complexity is O(n) to store the DP array.