LeetCode 1259 - Handshakes That Don't Cross

LeetCode Problem 1259

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming

Solution

Problem Understanding

In this problem, we are given an even number of people standing around a circle. Every person must participate in exactly one handshake, meaning the people are partitioned into pairs. The challenge is to count how many different ways these pairings can be formed such that no two handshakes cross when drawn as straight lines inside the circle.

For example, if there are 4 people labeled clockwise as 1, 2, 3, 4, there are exactly two valid non crossing configurations:

• (1,2) and (3,4)
• (1,4) and (2,3)

However, pairing (1,3) and (2,4) is invalid because the lines intersect.

The input is a single integer numPeople, which is always even. The output is the number of valid non crossing handshake arrangements modulo 10^9 + 7.

The constraints are important:

• 2 <= numPeople <= 1000
• numPeople is always even

Since the number of configurations grows very quickly, brute force enumeration becomes infeasible. The modulo requirement also signals that the answer can become extremely large.

An important observation is that the problem is structurally identical to counting valid parenthesis combinations or counting non crossing chord pairings in a circle. This leads directly to the Catalan number recurrence.

Several edge cases are important:

• The smallest input, numPeople = 2, has exactly one handshake arrangement.
• Large inputs like 1000 require an efficient dynamic programming solution.
• A naive recursive solution without memoization would explode exponentially.
• Since results become huge, modular arithmetic must be applied carefully during computation.

Approaches

Brute Force Approach

A brute force solution would attempt to generate every possible pairing of people and then check whether any two handshakes cross.

The process would look like this:

1. Pick one unpaired person.
2. Try pairing them with every other available person.
3. Recursively continue until everyone is paired.
4. For each completed pairing configuration, test whether any handshakes intersect.

This approach is correct because it explores every possible perfect matching and filters out the invalid crossing ones.

However, the number of pairings grows extremely fast. The count of perfect matchings among n people is:

$$(n-1)(n-3)(n-5)\dots 1$$

For numPeople = 1000, this is astronomically large. Even before checking crossings, generating all pairings is completely infeasible.

Optimal Dynamic Programming Approach

The key insight is that choosing one handshake splits the circle into two completely independent subproblems.

Suppose person 0 shakes hands with person k.

Because handshakes cannot cross:

• All people between 0 and k must pair internally.
• All people outside that interval must also pair internally.

This creates two smaller non crossing handshake problems.

If:

• Left side contains left people
• Right side contains right people

then the total number of configurations for this split is:

$$dp[left] \times dp[right]$$

Summing over every valid partner for person 0 gives the recurrence:

$$dp[n] = \sum dp[left] \times dp[right]$$

This is exactly the Catalan number recurrence.

The dynamic programming solution efficiently computes answers bottom up for all even values up to numPeople.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Generates all pairings and checks crossings
Optimal	O(n²)	O(n)	Dynamic programming using Catalan recurrence

Algorithm Walkthrough

1. Create a dynamic programming array dp of size numPeople + 1.

The value dp[i] represents the number of valid non crossing handshake arrangements for i people. 2. Initialize the base case.

There is exactly one way to arrange handshakes among zero people:

$$dp[0] = 1$$

This empty configuration is important because it allows multiplication in the recurrence. 3. Iterate through all even numbers of people from 2 to numPeople.

Odd numbers are ignored because it is impossible to pair everyone if the count is odd. 4. For each people, try pairing the first person with every possible valid partner.

If the first person pairs with person partner, then:

• The people inside the interval form one subproblem.
• The people outside the interval form another subproblem.

5. Compute the sizes of the two subproblems.

If the first person pairs with position partner:

• Left side size:

$$left = partner - 1$$

• Right side size:

$$right = people - partner - 1$$ 6. Multiply the number of ways for the left and right subproblems.

Since the two regions are independent:

$$dp[left] \times dp[right]$$

Add this contribution to dp[people]. 7. Apply modulo after every addition.

This prevents integer overflow and satisfies the problem requirement. 8. After filling the table, return dp[numPeople].

Why it works

Whenever one handshake is fixed, the non crossing condition forces the remaining handshakes into two independent regions. Every valid arrangement is uniquely formed by combining valid arrangements from those two smaller regions. The recurrence therefore counts every valid configuration exactly once and never counts invalid crossing arrangements.

Python Solution

class Solution:
    def numberOfWays(self, numPeople: int) -> int:
        MOD = 10**9 + 7

        dp = [0] * (numPeople + 1)
        dp[0] = 1

        for people in range(2, numPeople + 1, 2):
            for partner in range(1, people, 2):
                left = partner - 1
                right = people - partner - 1

                dp[people] += dp[left] * dp[right]
                dp[people] %= MOD

        return dp[numPeople]

The implementation directly follows the Catalan recurrence.

The dp array stores the number of valid configurations for every even number of people. The base case dp[0] = 1 represents the empty configuration.

The outer loop processes increasing even values of people. For each value, the inner loop selects a partner for the first person.

The partner index increases by 2 because the left side must contain an even number of people to allow complete pairing.

For every split:

• left counts people inside the chosen handshake
• right counts people outside it

The number of valid arrangements for this split is the product of the two independent subproblems.

Modulo arithmetic is applied after every update to keep numbers manageable.

Go Solution

func numberOfWays(numPeople int) int {
    const MOD int = 1e9 + 7

    dp := make([]int, numPeople+1)
    dp[0] = 1

    for people := 2; people <= numPeople; people += 2 {
        for partner := 1; partner < people; partner += 2 {
            left := partner - 1
            right := people - partner - 1

            dp[people] = (dp[people] + dp[left]*dp[right]) % MOD
        }
    }

    return dp[numPeople]
}

The Go implementation mirrors the Python solution closely.

A slice is used instead of a Python list. Since Go integers can overflow on some platforms, careful modulo operations are applied during every update.

The recurrence and iteration structure remain identical.

Worked Examples

Example 1

Input:

numPeople = 4

Initial state:

People	dp Value
0	1
2	0
4	0

Computing dp[2]

Only one possible partner:

Partner	Left	Right	Contribution
1	0	0	1 × 1 = 1

Result:

People	dp Value
2	1

Computing dp[4]

Partner = 1

Left	Right	Contribution
0	2	1 × 1 = 1

Partner = 3

Left	Right	Contribution
2	0	1 × 1 = 1

Total:

$$dp[4] = 1 + 1 = 2$$

Final answer:

2

Example 2

Input:

numPeople = 6

We already know:

People	dp Value
0	1
2	1
4	2

Computing dp[6]

Partner = 1

Left	Right	Contribution
0	4	1 × 2 = 2

Partner = 3

Left	Right	Contribution
2	2	1 × 1 = 1

Partner = 5

Left	Right	Contribution
4	0	2 × 1 = 2

Total:

$$dp[6] = 2 + 1 + 2 = 5$$

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Nested loops over even person counts and partner choices
Space	O(n)	Dynamic programming table of size numPeople + 1

The outer loop iterates through approximately n/2 even values. For each value, the inner loop also iterates up to n/2 times. This produces quadratic time complexity.

The only additional memory used is the dp array, which stores one integer per possible person count.

Test Cases

solution = Solution()

assert solution.numberOfWays(2) == 1   # Smallest valid input
assert solution.numberOfWays(4) == 2   # Example 1
assert solution.numberOfWays(6) == 5   # Example 2
assert solution.numberOfWays(8) == 14  # Catalan number C4
assert solution.numberOfWays(10) == 42 # Catalan number C5
assert solution.numberOfWays(12) == 132 # Larger Catalan value
assert solution.numberOfWays(14) == 429 # Another standard Catalan number
assert solution.numberOfWays(1000) > 0 # Large stress test

Test	Why
numPeople = 2	Validates smallest base case
numPeople = 4	Verifies first nontrivial configuration count
numPeople = 6	Confirms recurrence behavior
numPeople = 8	Checks Catalan sequence progression
numPeople = 10	Validates larger DP transitions
numPeople = 12	Ensures correctness for deeper recursion structure
numPeople = 14	Confirms continued Catalan growth
numPeople = 1000	Stress tests performance and modulo handling

Edge Cases

One important edge case is the smallest possible input, numPeople = 2. There is only one possible handshake, so the answer must be 1. Implementations that forget to initialize dp[0] = 1 often fail this case because the recurrence depends on empty subproblems contributing multiplicatively.

Another important case is very large input values such as numPeople = 1000. The number of configurations becomes enormous, far exceeding normal integer ranges. Without applying modulo arithmetic during every update, overflow issues would occur in many languages. The implementation safely applies % MOD after each addition.

A subtle edge case involves ensuring only even sized subproblems are considered. If the partner selection were incorrect, the algorithm could generate odd sized regions that cannot be fully paired. By iterating partners in steps of 2, both resulting subproblems always contain even numbers of people, guaranteeing valid recursive structure.

A final edge case concerns empty subproblems. When the first person pairs with the immediate neighbor or the last person, one side of the split contains zero people. The algorithm handles this naturally because dp[0] = 1, correctly representing one valid empty arrangement.