⚡Flashcard Drill➔
NeetCode #665LC-1259Hard1-D Dynamic ProgrammingNC Algo100
← Back to All Problems

#665 · #1259 · Handshakes That Don't Cross(不相交的握手)

📌 Problem Statement & Constraints

numPeople people stand in a circle and each shakes exactly one other person's hand, with no two handshakes crossing. Return the number of ways to do this, modulo 10^9 + 7. Constraints: 1 <= numPeople <= 1000, and numPeople is even.

💡 Core Algorithmic Approaches

  1. Fix person 0; their partner must be at an odd offset so that the two arcs formed have even lengths.
  2. If person 0 partners with person k, the circle splits into two independent arcs of k - 1 and numPeople - k - 1 people, whose handshakes cannot interact.
  3. So dp[n] = sum(dp[k - 1] * dp[n - k - 1]) over odd k from 1 to n - 1, with dp[0] = 1.
  4. These are the Catalan numbers; the modulo keeps the values bounded.

💻 Benchmark Python3 Implementation

class Solution:
    def numberOfWays(self, numPeople: int) -> int:
        MOD = 10**9 + 7
        n = numPeople
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(2, n + 1, 2):   # only even numbers of people are valid
            total = 0
            for k in range(1, i, 2):   # partner of person 0 splits the arc evenly
                total += dp[k - 1] * dp[i - k - 1]
            dp[i] = total % MOD
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): the nested loops over even sizes and split points.
💾 Space Complexity
O(n): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Partnering person 0 with an even-offset person: the partner must be at an odd offset so both arcs contain an even number of people.
  • Forgetting the modulo: the counts grow like Catalan numbers and overflow fixed-width integers.
  • Treating the arrangement as a line: fixing person 0 and splitting the circle is what makes the recursion valid.
  • Iterating i over every value: odd i are meaningless because a perfect matching needs an even count.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems