We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Handshakes That Don't Cross

Number: 1213

Difficulty: Hard

Paid? Yes

Companies: Amazon

Problem Description

Given an even number of people arranged in a circle, each person shakes hands with someone else in such a way that exactly numPeople / 2 handshakes occur. The handshakes must be arranged so that no two handshakes cross. Return the number of valid handshake arrangements modulo 10^9 + 7.

Key Insights

  • The problem is equivalent to counting the number of non-crossing perfect matchings in a circle.
  • This count is given by the Catalan numbers; specifically, the nth Catalan number when n = numPeople / 2.
  • A dynamic programming (DP) approach can be used where dp[i] represents the number of valid arrangements for 2*i people.
  • The recurrence relation is: dp[i] = Σ (dp[j] * dp[i - 1 - j]) for all j from 0 to i-1.
  • The modulo operation is applied at every step to keep numbers within bounds.

Space and Time Complexity

Time Complexity: O(n^2) where n = numPeople / 2
Space Complexity: O(n) for the DP array

Solution

We use a DP array where dp[0] is set to 1 (base case with 0 pairs). For each number of pairs i from 1 up to numPeople / 2, we compute dp[i] by iterating j from 0 to i-1 and summing up the product dp[j] * dp[i - 1 - j]. Each multiplication and addition is taken modulo 10^9 + 7. This approach builds the solution using the Catalan number recurrence relation iteratively.

Code Solutions

# Python Solution
def numberOfWays(numPeople):
    MOD = 10**9 + 7
    n = numPeople // 2  # number of handshake pairs
    dp = [0] * (n + 1)
    dp[0] = 1  # base case: only 1 way to arrange 0 pairs

    # Build the DP array using the Catalan number recurrence
    for i in range(1, n + 1):
        dp[i] = 0
        for j in range(i):
            # Multiply the number of ways for the left and right segments and add to dp[i]
            dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % MOD
    return dp[n]

# Example usage:
print(numberOfWays(4))  # Output: 2
← Back to All Questions