Skip to main content
Talentd

Handshakes That Don't Cross - Solution & Explanation

HardPremiumFree on FleetCodeMathDynamic Programming8 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 1000
  • numPeople is 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 return 1.
  • 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 be r=i-l-2. Then we have dfs(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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Recursive PairingO(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 ProgrammingO(n^2)O(n)Iterative DP preferred when avoiding recursion or stack overhead
Catalan Number FormulaO(n)O(n)When factorials and modular inverses are precomputed for fast combinatorial calculation

Video Solution

1259 Handshakes That Don't Cross (Biweekly Contest 13) • Kelvin Chandra • 2,800 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Handshakes That Don't Cross with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer