Handshakes That Don't Cross - Practice Coding Problems

Handshakes That Don't Cross - Problem

You are given an even number of people numPeople that stand around a circle. Each person must shake hands with exactly one other person, resulting in 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.

Two handshakes cross if the line segments connecting the pairs of people intersect when drawn inside the circle.

Input & Output

Example 1 — Basic Case

$ Input: numPeople = 4

› Output: 2

💡 Note: Person 0 can shake hands with person 1 (leaving 2,3 as a pair) or with person 3 (leaving 1,2 as a pair). Both arrangements have no crossing handshakes.

Example 2 — Larger Circle

$ Input: numPeople = 6

› Output: 5

💡 Note: With 6 people in a circle, there are 5 different ways to arrange 3 handshakes without any crossings. This corresponds to the 3rd Catalan number.

Example 3 — Minimum Case

$ Input: numPeople = 2

› Output: 1

💡 Note: Only one way exists: the two people shake hands with each other. No crossings possible.

Constraints

2 ≤ numPeople ≤ 1000
numPeople is even

Visualization

Tap to expand

Understanding the Visualization

Input

4 people arranged in a circle

Process

Find all ways to pair without crossings

Output

Count = 2 valid arrangements

Key Takeaway

🎯 Key Insight: This problem follows the Catalan number sequence - a fundamental pattern in combinatorics representing non-crossing structures.

Asked in

G Google 15 M Microsoft 12 F Facebook 8

The key insight is recognizing this as a Catalan number problem. Each valid handshake arrangement corresponds to a way of parenthesizing expressions or building binary trees. Best approach uses the mathematical Catalan formula for O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(n²)	O(n)	Cache recursive results to avoid redundant calculations
Recursive Brute Force	O(4ⁿ)	O(n)	Try all possible ways to pair the first person and recurse
Catalan Number Formula	O(n)	O(1)	Apply direct mathematical formula for Catalan numbers
Bottom-up Dynamic Programming	O(n²)	O(n)	Build solution iteratively using tabulation

Recursive with Memoization — Algorithm Steps

Create a memoization cache
For each subproblem, check cache first
If not cached, calculate recursively
Store result in cache before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate

Compute result for subproblem size n

Store

Cache the result in memo table

Reuse

Return cached result for future queries

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

const int MOD = 1000000007;
long long memo[1001];
int initialized = 0;

long long countWays(int n) {
    if (!initialized) {
        memset(memo, -1, sizeof(memo));
        initialized = 1;
    }
    
    if (n <= 2) return 1;
    
    if (memo[n] != -1) return memo[n];
    
    long long total = 0;
    for (int i = 1; i < n; i += 2) {
        int left = i - 1;
        int right = n - i - 1;
        total = (total + countWays(left) * countWays(right)) % MOD;
    }
    
    memo[n] = total;
    return total;
}

int solution(int numPeople) {
    return countWays(numPeople);
}

int main() {
    int numPeople;
    scanf("%d", &numPeople);
    printf("%d\n", solution(numPeople));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of the n/2 subproblems is calculated once, with O(n) work per subproblem

⚠ Quadratic Growth

Space Complexity

O(n)

Memoization cache stores results for each subproblem size plus recursion stack

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler