LeetCode 1259: Handshakes That Don't Cross Solution

Master LeetCode problem 1259 (Handshakes That Don't Cross), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1259. Handshakes That Don't Cross

Hard

Math Dynamic Programming

Problem Explanation

Explanation:

The problem asks us to find the number of ways to perform handshakes between people such that no two handshakes cross each other. This can be modeled as finding the number of ways to pair up n people where each person shakes hands with exactly one other person in a non-crossing way.

To solve this problem, we can use dynamic programming. Let's define a function dp[i] which represents the number of ways to pair up i people without any crossing handshakes. We can build up this function iteratively starting from i=2 up to n.

For each i, we can iterate over all possible ways to split the i people into two groups, and then recursively calculate the number of ways to pair up those two groups. The total number of ways for i people can be obtained by summing up the product of the number of ways for the two groups.

The base cases would be dp[0] = 1 and dp[2] = 1 since there is only one way to pair up 2 people without crossing. :

Solution Code

class Solution {
    public int numberOfWays(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[2] = 1;
        
        for (int i = 4; i <= n; i += 2) {
            for (int j = 0; j < i; j += 2) {
                dp[i] += dp[j] * dp[i - j - 2];
                dp[i] %= 1000000007;
            }
        }
        
        return (int)dp[n];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1259 (Handshakes That Don't Cross)?

This page provides optimized solutions for LeetCode problem 1259 (Handshakes That Don't Cross) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1259 (Handshakes That Don't Cross)?

The time complexity for LeetCode 1259 (Handshakes That Don't Cross) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1259 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1259 in Java, C++, or Python.

Back to LeetCode Solutions