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.

Description Hints 3 Solution Video 6:08

1259. Handshakes That Don't Cross

Hard61.1% acceptance1 companyPremium elsewhere, free here

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 10⁹ + 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.

Asked at 1 company

Amazon

Topics

Dynamic Programming Math

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Let dp[n] be the number of ways that n people can handshake.

Hint 3

Then fix a person as a pivot and turn for every other person who will have a handshake, the answer is the sum of the products of the new two subproblems.

6:08

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution