Handshakes That Don't Cross

Hard

Asked by:

23 views

Topics:

Dynamic Programming

You are given an even number numPeople representing the number of people sitting around a round table. The people are numbered from 1 to numPeople in a clockwise direction.

You need to build the minimum number of handshakes so that each person shakes the hand of someone else, and no handshakes cross. In other words, if person i shakes the hand of person j, then there is no person k such that i < k < j where person k is shaking the hand of someone else.

Return the number of possible ways of doing it.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: numPeople = 2
Output: 1
Explanation: There is only one way to form a handshake between person 1 and person 2.

Example 2:

Input: numPeople = 4
Output: 2
Explanation: There are two ways to form a handshake between people:
- First way: person 1 shakes the hand of person 2, and person 3 shakes the hand of person 4.
- Second way: person 1 shakes the hand of person 4, and person 2 shakes the hand of person 3.

Example 3:

Input: numPeople = 6
Output: 5

Constraints:

2 <= numPeople <= 1000
numPeople is even.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of people (N) participating in the handshake?
Is N always an even number?
Should I return the number of ways as an integer, or could it potentially overflow and require a different data type?
If N is zero, should I return 1 or 0?
Are we only concerned with handshakes that don't cross, or should I also consider arrangements where all people shake hands with someone?

Brute Force Solution

Approach

The core idea behind the brute force approach is to explore every single possible way people can shake hands. We check each way to see if any handshakes cross each other, and count the number of ways where the handshakes don't cross.

Here's how the algorithm would work step-by-step:

Consider the first person and try every possible person they could shake hands with.
For each handshake, look at the people remaining.
Within those remaining people, again try every possible pairing for handshakes.
Continue this process until everyone has shaken hands with someone.
Each time we find a complete set of handshakes, check if any of the handshakes cross each other.
If no handshakes cross, count this arrangement as a valid way.
Do this for every possible combination of handshakes from the very beginning, and in the end, you'll have counted all the valid, non-crossing handshake arrangements.

Code Implementation

def handshakes_that_dont_cross_brute_force(number_of_people):
    total_non_crossing_handshakes = 0

    def is_crossing(handshake_one, handshake_two):
        person_one_handshake_one, person_two_handshake_one = handshake_one
        person_one_handshake_two, person_two_handshake_two = handshake_two

        return (person_one_handshake_one < person_one_handshake_two < person_two_handshake_one < person_two_handshake_two) or \
               (person_one_handshake_two < person_one_handshake_one < person_two_handshake_two < person_two_handshake_one)

    def check_for_crossing_handshakes(all_handshakes):
        for i in range(len(all_handshakes)):
            for j in range(i + 1, len(all_handshakes)):
                if is_crossing(all_handshakes[i], all_handshakes[j]):
                    return True
        return False

    def find_all_possible_handshakes(remaining_people, current_handshakes):
        nonlocal total_non_crossing_handshakes

        # Base case: If everyone has shaken hands.
        if not remaining_people:
            # Checks to make sure there are no crossed handshakes
            if not check_for_crossing_handshakes(current_handshakes):
                total_non_crossing_handshakes += 1
            return

        # Choose the first person in the remaining people.
        first_person = remaining_people[0]

        # Iterate through the remaining people to find a handshake partner.
        for second_person in remaining_people[1:]:
            # Create new handshake
            new_handshake = (first_person, second_person)

            # Create the list of people left after handshake.
            remaining_after_handshake = remaining_people[1:].copy()
            remaining_after_handshake.remove(second_person)

            # Recursively find handshakes with reduced list of people
            find_all_possible_handshakes(
                remaining_after_handshake,
                current_handshakes + [new_handshake],
            )

    # Start the recursion with all people and an empty list of handshakes.
    all_people = list(range(number_of_people))
    # Begin by determining the base handshake combinations
    find_all_possible_handshakes(all_people, [])

    return total_non_crossing_handshakes

Big(O) Analysis

Time Complexity

O(4^n / n^(3/2)) – The brute force approach explores every possible handshake pairing. For 2n people, the first person can shake hands with any of the 2n-1 others. This choice divides the remaining people into two groups. The number of ways to arrange handshakes within each group is calculated recursively. The total number of ways can be represented by Catalan numbers, which grow as 4^n / (n * sqrt(n)). Checking for crossing handshakes in each arrangement adds a factor that is less impactful to overall complexity than the number of arrangements, so the dominant term remains based on the Catalan number growth. Therefore, the Big O time complexity is O(4^n / n^(3/2)).

Space Complexity

O(N) – The brute force approach described explores all possible handshake combinations recursively. The depth of the recursion can be as large as N, where N is the number of people (since each handshake pairing reduces the number of remaining people to pair). Each level of the recursion requires storing variables representing the state of the current handshake configuration on the call stack. Therefore, the space complexity is proportional to the maximum depth of the recursion, which is O(N).

Optimal Solution

Approach

The key to solving this problem efficiently is to recognize a pattern that allows us to break down the problem into smaller, self-similar subproblems. We use a clever idea involving arranging things in a specific order and calculating the number of ways to do it without any overlaps.

Here's how the algorithm would work step-by-step:

Notice that if you have a certain number of people standing in a circle, the first person must shake hands with someone.
Realize that this handshake divides the remaining people into two groups.
Think of the number of ways the people within each of these two groups can shake hands among themselves, without crossing any handshakes.
Recognize that the total number of ways for the whole group to shake hands is the product of the number of ways for each of the two smaller groups, plus the initial handshake.
Keep breaking down each group into even smaller groups by considering who the first person shakes hands with.
Eventually, you'll get down to groups so small that the answer is obvious (for example, if there are zero or two people, there's only one way for them to shake hands).
Work backwards, putting the results of the smaller groups together to calculate the number of ways for the larger groups, until you get to the original number of people.
This structured breakdown avoids checking every single handshake combination, leading to a much faster solution.

Code Implementation

def number_of_handshakes_that_dont_cross(number_of_people):
    catalan_numbers = [0] * (number_of_people // 2 + 1)
    catalan_numbers[0] = 1

    # Base case: 0 people can shake hands in 1 way
    for number_of_pairs in range(1, number_of_people // 2 + 1):
        for j in range(number_of_pairs):
            # Summing products of smaller subproblems.
            catalan_numbers[number_of_pairs] += catalan_numbers[j] * catalan_numbers[number_of_pairs - 1 - j]

    # The nth Catalan number gives the answer
    return catalan_numbers[number_of_people // 2]

Big(O) Analysis

Time Complexity

O(n) – The provided approach outlines a dynamic programming solution. The outer loop iterates from 1 to n (number of people) to build up the solution array. Within the loop, the calculation to populate each dp[i] value involves summing products of previous dp values, resulting in another loop that iterates up to i. Although there is a nested summing within the dynamic programming calculation, the number of operations is proportional to calculating n Catalan numbers using the formula, which simplifies to O(n) when memoization is used as each subproblem is solved once. Therefore, overall time complexity for handshakes calculation is O(n).

Space Complexity

O(N) – The plain English explanation implies a recursive breakdown of the problem into smaller subproblems. Each recursive call adds a frame to the call stack to store local variables and the return address. The maximum depth of this recursion is proportional to N, where N is the number of people. Therefore, the auxiliary space used by the recursion stack is O(N).

Edge Cases

Case	How to Handle
Zero people (N=0)	Return 1, as there is one way to arrange no handshakes.
One person (N=1)	Return 1, as with one person, there are no handshakes to calculate.
Large N leading to potential integer overflow	Use a data type that can accommodate large numbers (e.g., long in Java/C++, arbitrary-precision integers in Python).
Odd number of people	Return 0, since it is impossible to have each person shake hands if there is an odd number of people.
N close to maximum integer limit	Ensure the data type chosen has sufficient range to calculate Catalan numbers for the given input, preventing overflow.
Negative N	Throw an IllegalArgumentException or return an error value indicating invalid input.
Non-integer input for N	Cast input to the appropriate integer type, or throw an error if the input cannot be reasonably converted.
Recursive implementation leading to stack overflow with large N	Convert the recursive solution to an iterative dynamic programming solution to avoid stack overflow.

Zero people (N=0)

How to Handle:

Return 1, as there is one way to arrange no handshakes.

One person (N=1)

How to Handle:

Return 1, as with one person, there are no handshakes to calculate.

Large N leading to potential integer overflow

How to Handle:

Use a data type that can accommodate large numbers (e.g., long in Java/C++, arbitrary-precision integers in Python).

Odd number of people

How to Handle:

Return 0, since it is impossible to have each person shake hands if there is an odd number of people.

N close to maximum integer limit

How to Handle:

Ensure the data type chosen has sufficient range to calculate Catalan numbers for the given input, preventing overflow.

Negative N

How to Handle:

Throw an IllegalArgumentException or return an error value indicating invalid input.

Non-integer input for N

How to Handle:

Cast input to the appropriate integer type, or throw an error if the input cannot be reasonably converted.

Recursive implementation leading to stack overflow with large N

How to Handle:

Convert the recursive solution to an iterative dynamic programming solution to avoid stack overflow.