1259. Handshakes That Don't Cross

Problem Description

In the given problem, we have numPeople, a number representing an even number of people standing in a circle. The task is to calculate the number of different ways these people can perform handshakes. The condition is that each person shakes hands with exactly one other person, resulting in numPeople / 2 handshakes in total. The twist here is that handshakes are not allowed to cross over each other. If we illustrate people as points on the circumference of the circle and handshakes as chords connecting these points, we must find the number of ways to draw these chords so that none intersect. Because the number of potential handshakes can be extremely large, the answer should be returned modulo 10^9 + 7.

Intuition

The problem can be approached by using the concept of Catalan Numbers which are used in combinatorial mathematics. The nth Catalan number counts the number of ways to form non-intersecting handshakes among 'n' pairs of people standing in a circle, which is exactly the scenario described by the problem.

The intuition for the solution is to use dynamic programming due to the overlapping subproblems observed. The process starts with the basic understanding that any handshake splits the circle into two independent subproblems.

This is because once any two people shake hands, those inside the handshake cannot affect those outside and vice versa. Therefore, we can recursively calculate the number of ways for the left and right groups formed by each handshake and multiply them. Summing these products for each possible initial handshake (choosing pairs in turns) will give the total number of ways for numPeople.

The use of memoization (via Python's @cache decorator) optimizes the solution by storing results of the subproblems so that they don't need to be recalculated multiple times.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The reference solution uses a recursive approach with dynamic programming to efficiently calculate the number of non-crossing handshake combinations in a circle of numPeople. Here’s a step-by-step breakdown of the algorithm:

Dynamic Programming and Cache: The @cache decorator is used for memoization, which stores the results of the recursive function dfs to avoid recalculating them. This is essential for improving the efficiency as dfs will be called with the same parameters multiple times.
Recursive Function dfs: This function takes a single argument i, representing the number of people left to be paired for handshakes. The base case is when i is less than or equal to 1 (i.e., when there are no people or just one person left), the function returns 1 because there is only one way (or none, respectively) to organize the handshakes.
Iterating Over Possible Pairings:
- Inside the recursive function, a loop iterates over every possible pairing of two people. The loop variable l represents the number of people in the left subproblem, which is incremented by 2 each time to ensure pairs are formed.
- For each pair formed by people l and l+1, a subproblem to the left with l people and a subproblem to the right with i - l - 2 people are created.
Calculating Subproblems:
- For each pairing, the number of ways to organize handshakes is recursively calculated for both the left and the right subproblems. This corresponds to the number of ways people within each subproblem can shake hands without crossings.
Combining Results and Applying Modulo:
- The results from the left and right subproblems are multiplied to get the total number of combinations that include that specific pairing. This is because the subproblems are independent, and the combination of their handshakes leads to a valid overall arrangement.
- The running total ans is updated by adding this product. A modulo operation is applied to ans to ensure that the number stays within bounds specified by the problem (10^9 + 7).
Returning the Result:
- Finally, the recursive function returns the total sum ans modulo 10^9 + 7.

The main function numberOfWays calls dfs with numPeople as the argument to initiate the algorithm and returns the result, which is the total count of handshake configurations modulo 10^9 + 7.

The solution effectively uses the divide-and-conquer strategy to reduce the complex problem into simpler, smaller instances. The memoization ensures that the overall time complexity is kept in check, with each subproblem being solved only once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the solution approach outlined above. Suppose numPeople is 4, which means we have 4 people standing in a circle.

First, we visualize these 4 people as points on a circle. Here are the steps we would follow:

Dynamic Programming and Cache Initialization: Before we dive into the recursion, the @cache decorator prepares the function to store any result computed for a specific number of people, which avoids redundant calculations.
Calling the Recursive Function: We call our recursive function dfs(4) since we want to calculate the number of ways 4 people can shake hands without crossing handshakes.
Recursive Case dfs(i): The function takes i = 4 as the number of people left to be paired.
- Base cases (i < 2) return 1 but i is 4, so we proceed with recursion.
Iterating Over Possible Pairings:
- We consider dividing the problem into subproblems. We start with person 0 and we try to make a pair with every other person, forming two subproblems per pair.
- We have two possible pairings to consider: (0,1) and (0,2). Note that (0,3) would create a single subproblem without sub-divisions, which is implicitly included in the other pairings.
Calculating Subproblems for Pair (0,1):
- Choosing the pair (0,1) creates two subproblems: left with 0 people and right with 2 people (dfs(2)).
- dfs(2) is a smaller instance of the problem where the base case applies: there is exactly 1 way for 2 people to shake hands without any crossings.
Calculating Subproblems for Pair (0,2):
- Choosing the pair (0,2) creates two subproblems: left with 2 people (dfs(2)) and right with 0 people.
- As above, dfs(2) returns 1 since there's only 1 way to pair 2 people without crossings.
Combining Results and Applying Modulo:
- For pair (0,1), the total for the subproblems is 1 (left) * 1 (right) = 1.
- For pair (0,2), the total for the subproblems is 1 (left) * 1 (right) = 1.
- We sum these up, which gives us 1 + 1 = 2, the total number of non-intersecting handshake combinations for 4 people.
Returning the Result:
- As there are no more pairs to evaluate, the function would return 2.

When the main function calls dfs(4), it would ultimately return the result of 2 as the count of handshake configurations for 4 people, modulo 10^9 + 7 (though in this small example, the modulo operation is not necessary).

This illustrates the efficiency of the dynamic programming approach; even though the number of potential configurations can grow rapidly with more people, each subproblem is only solved once and reused as needed, yielding a much faster overall solution.

Solution Implementation

1from functools import lru_cache  # Import the caching decorator
2
3class Solution:
4    def numberOfWays(self, numPeople: int) -> int:
5        # Define a modulo constant for the results.
6        MOD = 10**9 + 7
7
8        # Use the lru_cache to memoize the previous results.
9        @lru_cache(maxsize=None)
10        def count_ways(people_left: int) -> int:
11            # If no person or only one person is left, only one way is possible (base case).
12            if people_left < 2:
13                return 1
14          
15            # Initialize answer for this subproblem.
16            answer = 0
17
18            # Loop through the people by pairs, with a step of 2 because each person must be paired.
19            for left_end in range(0, people_left, 2):
20                # The right_end is calculated based on how many are to the left and subtracting 2 for
21                # the partners in the current pair.
22                right_end = people_left - left_end - 2
23              
24                # Calculate the ways by taking the product of ways for the left and right subproblems.
25                answer += count_ways(left_end) * count_ways(right_end)
26                # Apply the modulo at each step to keep the number within the integer limit.
27                answer %= MOD
28          
29            # Return the computed answer for this subproblem.
30            return answer
31      
32        # Start the recursion with the total number of people.
33        return count_ways(numPeople)
34
35# You can execute the code like this:
36# solution = Solution()
37# result = solution.numberOfWays(numPeople)
38# where `numPeople` is the number of people you want to find the number of ways for.
39

1class Solution {
2    private int[] cache; // Cache the results to avoid recomputation
3    private final int MOD = (int)1e9 + 7; // Modulo constant for large numbers
4
5    public int numberOfWays(int numPeople) {
6        cache = new int[numPeople + 1]; // Initialize cache with the number of people
7        return dfs(numPeople); // Use DFS to calculate the number of ways
8    }
9
10    // Helper method to compute the number of ways recursively
11    private int dfs(int n) {
12        // Base case: no people or a single pair
13        if (n < 2) {
14            return 1;
15        }
16        // Return cached value if already computed
17        if (cache[n] != 0) {
18            return cache[n];
19        }
20        // Iterate over possible splits with every second person
21        for (int left = 0; left < n; left += 2) {
22            int right = n - left - 2; // Number of people on the right side
23            // Combine ways of left and right side under modulo
24            cache[n] = (int)((cache[n] + (long)dfs(left) * dfs(right) % MOD) % MOD);
25        }
26        return cache[n]; // Return the total number of ways for n people
27    }
28}
29

1class Solution {
2public:
3    // Method to calculate the number of ways to form handshakes without crossing hands
4    // "numPeople" is the number of people forming handshakes
5    int numberOfWays(int numPeople) {
6        const int MOD = 1e9 + 7; // Modulo to prevent integer overflow
7        vector<int> dp(numPeople + 1, 0); // Create a dynamic programming table initialized to 0
8      
9        // Lambda function to calculate the number of ways using recursion and dynamic programming
10        function<int(int)> countWays = [&](int n) {
11            // Base case: for 0 or 2 people there's only one way to perform handshake (0: no one, 2: one handshake possible)
12            if (n < 2) {
13                return 1;
14            }
15            // If already computed, return the stored result to avoid re-computation
16            if (dp[n] != 0) {
17                return dp[n];
18            }
19            // Iterate over all possible even partitions of the n-people group
20            for (int left = 0; left < n; left += 2) {
21                int right = n - left - 2;
22                // Recursively compute combinations for left and right partitions, then combine for total
23                dp[n] = (dp[n] + (1LL * countWays(left) * countWays(right)) % MOD) % MOD;
24            }
25            // Return the result for n people
26            return dp[n];
27        };
28
29        // Start the recursion with the total number of people
30        return countWays(numPeople);
31    }
32};
33

1// Function to calculate the number of non-crossing handshakes for a given number of people
2function numberOfWays(numPeople: number): number {
3    const modulo = 10 ** 9 + 7; // Define module for large number arithmetic to prevent overflow
4    const dp: number[] = Array(numPeople + 1).fill(0); // Initialize dynamic programming table with zeros
5  
6    // Define a helper function using DFS to find the number of ways to complete non-crossing handshakes
7    const findWays = (peopleLeft: number): number => {
8        if (peopleLeft < 2) { // Base case: if nobody or only one person is left, there is only one way
9            return 1;
10        }
11      
12        // Check if we have already computed the value for the current number of people
13        if (dp[peopleLeft] !== 0) {
14            return dp[peopleLeft];
15        }
16      
17        // Iterate through the problem reducing it into subproblems
18        for (let left = 0; left < peopleLeft; left += 2) {
19            const right = peopleLeft - left - 2;
20            // Calculate the number of ways by multiplying the subproblems and apply modulo
21            dp[peopleLeft] += Number((BigInt(findWays(left)) * BigInt(findWays(right))) % BigInt(modulo));
22            dp[peopleLeft] %= modulo; // Apply modulo to keep the number within the integer range
23        }
24      
25        return dp[peopleLeft];
26    };
27  
28    // Invoke the helper function with numPeople to find the result
29    return findWays(numPeople);
30}
31

Time and Space Complexity

The provided code solves the problem by using dynamic programming with memoization. Here is the analysis of the time complexity and space complexity:

Time Complexity

The dfs function essentially calculates the number of ways to pair numPeople people such that they form numPeople / 2 pairs. Each person can choose a partner from the remaining numPeople - 1 people, and then the problem is reduced to solving for numPeople - 2. However, due to the memoization (@cache), each subproblem is solved only once. The total number of subproblems corresponds to the number of even numbers from 0 to numPeople - 2, which is approximately numPeople/2.

For every call to dfs(i), we iterate over all even values less than i, doing constant work each time, and each recursive call is to a problem size that is strictly smaller than the current problem, leading to a recursion tree of height numPeople/2.

Considering all of these factors, the time complexity is O(n^2) where n is numPeople/2, because there will be n layers of recursion and each layer requires summing up n subproblem results. Therefore, when n is numPeople, the time complexity is O((n/2)^2) which simplifies to O(n^2).

Space Complexity

The space complexity is dominated by the memory used for storing the intermediate results in the cache. Since there are n/2 layers of recursion, with each layer requiring constant space plus the call stack, the space complexity is O(n), where n is numPeople/2.

Additionally, each recursive call uses a stack frame, but since we only make a new call after finishing with the previous call, the depth of the call stack will never exceed n/2. Therefore, taking the call stack into account does not change the overall space complexity, which remains O(n).

Combining these observations, the overall space complexity of the algorithm is O(n), where n is numPeople/2. Simplifying, we refer to it simply as O(n).

In the above analysis, n refers to the numPeople variable.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: