1434. Number of Ways to Wear Different Hats to Each Other


Problem Description

In this problem, you are given n people and a fixed collection of 40 different types of hats, each type has its unique label ranging from 1 to 40. A 2D integer array hats represents the hat preferences for each person, such that hats[i] contains a list of all the hats preferred by the i-th person. Your task is to determine the total number of unique ways that these n people can wear these hats so that no two people are wearing the same type of hat.

This is a classic combinatorial problem with a restriction that ensures the uniqueness of the hat type for each individual. The problem asks you to return this total number of unique distributions modulo 10^9 + 7, which is a common technique to manage large output values in computational problems, ensuring the result stays within the limits of standard integer data types.

Intuition

At its core, the solution to this problem is rooted in combinatorics and dynamic programming (DP). The intuition behind using dynamic programming comes from two key observations:

  1. The number of people n is small enough (maximum 10) to consider the problem using state space representation where each state represents a set of people who have already been assigned a hat. This allows us to compress the state into a binary number (for instance, a binary representation where each bit represents whether a person has been assigned a hat or not).

  2. The solution builds upon subproblems where each subproblem considers one less hat. This helps in constructing the final solution iteratively as DP excels at optimizing problems where the solution can be built from smaller subproblems.

Given the small number of people, we can use bit masks to represent who has a hat already. The dynamic programming array f[i][j] signifies the number of ways to assign hats up to the i-th hat, considering the people configuration j. The bit representation of j has '1' in the positions of people who have already been assigned hats and '0' otherwise.

The DP approach then incrementally builds up the solution by considering cases where either the i-th hat is not used or it's assigned to one of the people who like it following the rules.

Each state transition thus involves either:

  • Keeping the configuration as is (not assigning the new hat), which doesn't change the state, or
  • Including a new assignment (giving the i-th hat to person k), which changes the state by updating the bit mask to reflect that person k now has a hat.

This way, the final answer is built up by considering all the possibilities, taking into account which hats can be worn by whom, until all hats up to the maximum value in the given lists are processed.

Learn more about Dynamic Programming and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The implementation of the solution for this problem utilizes dynamic programming (DP) with bit masking and involves a few steps:

  1. Initialize the DP Table: A 2-dimensional DP table f is created with dimensions (m + 1) x (1 << n), where m is the maximum hat number preferred by any person and n is the number of people. Each entry f[i][j] will store the count of ways to distribute the first i types of hats across the people represented by state j.

  2. Define the Base Case: We start with the base case f[0][0] = 1, which means there is one way to assign zero hats to zero people.

  3. Map Preferences: We create a mapping g from each hat to a list of people who like that hat. The mapping is needed to quickly find which people can be considered when trying to distribute a particular hat.

  4. Iterate Over Hats: For each hat type from 1 to m, we iterate to assign this hat to different people. For each state j that represents which people already have hats, we can have two possibilities:

    • Hat not assigned: If the current hat is not assigned to anyone, then the number of ways to distribute hats remains the same as the previous hat, so f[i][j] = f[i - 1][j].

    • Hat assigned: If the hat is assigned to one of the potential people who like it, each assignment will result in a new state from j to j ⊕ (1 << k) where denotes the XOR operation and (1 << k) denotes a bit mask with only the k-th bit set (meaning assigning the i-th hat to the k-th person). This operation toggles the k-th bit of j, so we accumulate these new ways into f[i][j] i.e., f[i][j] = (f[i][j] + f[i - 1][j ⊕ (1 << k)]) % mod.

  5. Modulo Operation: Since the number of ways can be large, we take every sum modulo 10^9 + 7 (stored in the variable mod) to keep the values within the limits of a 32-bit signed integer.

  6. Return the Result: After processing all hats, the result will be in f[m][2^n - 1], which represents all n people having different hats.

This DP approach exploits the concept of state transitions while considering all permutations of hat assignments, respecting the individual preferences and ensuring unique ownership of hat types across all the people. The use of bit masking is a clever trick to represent a set of states succinctly when the universe is small, which is typically harder to do when dealing with large sets or where relationships between elements are complex.

The algorithm complexity primarily depends on the number of hats (which is at most 40) and the number of people (the size of the bitmask, which is 2^n states). Although it looks like a large number, the small limitation of n makes this algorithm feasible.

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

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we have n = 2 people and m = 3 different types of hats. The hats preferred by the people are represented by the 2D array hats such that hats[0] = [1, 2] and hats[1] = [2, 3]. Our goal is to find the number of unique ways to distribute hats so that both people wear different hats from their preference list.

Step by Step Implementation:

  1. Initialize the DP Table: We create a 2-dimensional DP table f with dimensions (3 + 1) x (1 << 2) (since there are at most 3 types of hats and 2 people). The table is initialized with zeros, except for the base case f[0][0] = 1.

  2. Define the Base Case: As defined, f[0][0] = 1 means one way to assign zero hats to zero people.

  3. Map Preferences: We create a mapping g from each hat to the list of people who like that hat. From the preference list, we get g[1] = [0], g[2] = [0, 1], g[3] = [1].

  4. Iterate Over Hats:

    • For hat 1: Only person 0 likes this hat. We update f[1][1] to 1, which indicates that there's one way to assign hat 1 to person 0.

    • For hat 2: Both person 0 and person 1 like this hat. We can assign this hat to person 0 if person 0 hasn't been given a hat already, which means updating f[2][1] to f[1][0]. Similarly, we can assign hat 2 to person 1 if person 1 hasn't been given a hat already, updating f[2][2].

    • For hat 3: Only person 1 likes this hat. We update f[3][2] to f[2][0] because we can give hat 3 to person 1 if they have no hat yet.

  5. Modulo Operation: After each assignment, we perform f[i][j] = (f[i][j] + f[i - 1][j ⊕ (1 << k)]) % mod to keep numbers within the 32-bit signed integer limit.

  6. Return the Result: The result is f[3][3], which represents both people having different hats. In this example, f[3][3] should give us 2, indicating there are two ways to give hats to the people according to their preferences: Person 0 can wear hat 1 and Person 1 can wear hat 3 or Person 0 can wear hat 2 and Person 1 can wear hat 3.

Thus, the example helps us see how the dynamic programming table builds up solutions with different combinations using bit masks to represent states. The table f is updated by considering each hat and each combination of which people already have hats (states). This results in a final count of the number of unique ways to distribute hats so that no two people are wearing the same type of hat.

Not Sure What to Study? Take the 2-min Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Python Solution

1from collections import defaultdict
2
3class Solution:
4
5    def numberWays(self, hats: List[List[int]]) -> int:
6        # Create a mapping of which hat numbers are preferred by each person
7        preference_map = defaultdict(list)
8        for person_id, preferred_hats in enumerate(hats):
9            for hat in preferred_hats:
10                preference_map[hat].append(person_id)
11
12        # Define a modulo value for the answer
13        mod = 10**9 + 7
14      
15        # Determine the number of people
16        num_people = len(hats)
17      
18        # Find the maximum hat number to define the range of hats
19        max_hat_number = max(max(hat_list) for hat_list in hats)
20      
21        # Initialize a DP array where f[i][j] is the number of ways where
22        # i is the current hat number, and j is the bitmask representing
23        # the assignment status of hats to people (1 means assigned)
24        dp = [[0] * (1 << num_people) for _ in range(max_hat_number + 1)]
25      
26        # Base case: 0 ways with 0 hats assigned
27        dp[0][0] = 1
28
29        # Iterate through all hat numbers
30        for hat in range(1, max_hat_number + 1):
31            # Iterate through all possible combinations of people
32            for mask in range(1 << num_people):
33                # The number of ways to assign hats without the current hat
34                dp[hat][mask] = dp[hat - 1][mask]
35                # Try to assign the current hat to each person who prefers this hat
36                for person in preference_map[hat]:
37                    # Check if the current person has not already been assigned a hat
38                    if mask & (1 << person):
39                        # Add the number of ways to assign hats with 
40                        # the current person assigned the current hat
41                        dp[hat][mask] = (dp[hat][mask] + dp[hat - 1][mask ^ (1 << person)]) % mod
42
43        # Return the total number of ways to assign all hats to all people
44        return dp[max_hat_number][(1 << num_people) - 1]
45

Java Solution

1class Solution {
2    public int numberWays(List<List<Integer>> hats) {
3        // Number of friends
4        int numFriends = hats.size();
5        // Maximum hat number across all friends
6        int maxHatNumber = 0;
7      
8        // Determine the highest numbered hat
9        for (List<Integer> friendHats : hats) {
10            for (int hat : friendHats) {
11                maxHatNumber = Math.max(maxHatNumber, hat);
12            }
13        }
14
15        // Create an array to associate each hat with a list of friends who like it
16        List<Integer>[] hatToFriends = new List[maxHatNumber + 1];
17        Arrays.setAll(hatToFriends, k -> new ArrayList<>());
18      
19        // Populate hatToFriends lists with the indices of friends
20        for (int i = 0; i < numFriends; ++i) {
21            for (int hat : hats.get(i)) {
22                hatToFriends[hat].add(i);
23            }
24        }
25
26        // A modulus value for the result
27        final int MOD = (int) 1e9 + 7;
28      
29        // Dynamic programming table where 'f[i][j]' represents the number of ways to assign
30        // hats to the first 'i' hats such that 'j' encodes which friends have received hats
31        int[][] dpTable = new int[maxHatNumber + 1][1 << numFriends];
32      
33        // Base case: there's 1 way to assign 0 hats (none to anyone)
34        dpTable[0][0] = 1;
35      
36        // Build the table from the base case
37        for (int i = 1; i <= maxHatNumber; ++i) {
38            for (int j = 0; j < 1 << numFriends; ++j) {
39                // Start with the number of ways without the current hat
40                dpTable[i][j] = dpTable[i - 1][j];
41              
42                // Iterate through all friends who like the current hat
43                for (int friendIndex : hatToFriends[i]) {
44                    // Check if the friend hasn't been given a hat yet in combination 'j'
45                    if ((j >> friendIndex & 1) == 1) {
46                        // Add ways to assign hats from previous combination with one less hat,
47                        // ensuring that friend 'friendIndex' now has a hat
48                        dpTable[i][j] = (dpTable[i][j] + dpTable[i - 1][j ^ (1 << friendIndex)]) % MOD;
49                    }
50                }
51            }
52        }
53      
54        // Return the number of ways for the last hat and all friends (the full set bit mask)
55        return dpTable[maxHatNumber][(1 << numFriends) - 1];
56    }
57}
58

C++ Solution

1class Solution {
2public:
3    int numberWays(vector<vector<int>>& hats) {
4        int numPeople = hats.size(); // Number of people
5        int maxHatID = 0;           // Maximum hat ID
6        // Find the maximum hat ID to know the range of hat IDs available
7        for (auto& personHats : hats) {
8            maxHatID = max(maxHatID, *max_element(personHats.begin(), personHats.end()));
9        }
10        // Create a graph where each hat ID points to a list of people who like that hat
11        vector<vector<int>> hatToPeople(maxHatID + 1);
12        for (int i = 0; i < numPeople; ++i) {
13            for (int hat : hats[i]) {
14                hatToPeople[hat].push_back(i);
15            }
16        }
17
18        const int MOD = 1e9 + 7; // Modulo value for avoiding integer overflow
19        // f[i][j] will be the number of ways to assign hats considering first i hats 
20        // where j is a bitmask representing which people have already been assigned a hat
21        int dp[maxHatID + 1][1 << numPeople];
22        memset(dp, 0, sizeof(dp));
23        dp[0][0] = 1; // Base case: no hats assigned to anyone
24
25        // Iterate over all hats
26        for (int i = 1; i <= maxHatID; ++i) {
27            // Iterate over all possible assignments of hats to people
28            for (int mask = 0; mask < (1 << numPeople); ++mask) {
29                // The number of ways without assigning the current hat remains the same
30                dp[i][mask] = dp[i - 1][mask];
31                // Iterate over all the people who like the current hat
32                for (int person : hatToPeople[i]) {
33                    // If this person has not yet been assigned a hat
34                    if (mask & (1 << person)) {
35                        // Add the number of ways by assigning the current hat to this person and update it modulo MOD
36                        dp[i][mask] = (dp[i][mask] + dp[i - 1][mask ^ (1 << person)]) % MOD;
37                    }
38                }
39            }
40        }
41        // Return the number of ways to assign all hats to all people
42        return dp[maxHatID][(1 << numPeople) - 1];
43    }
44};
45

Typescript Solution

1function numberWays(hats: number[][]): number {
2    // Number of people
3    const numPeople = hats.length;
4    // Maximum hat number
5    const maxHatNumber = Math.max(...hats.flat());
6  
7    // Graph representing which people can wear which hats
8    const hatToPeopleGraph: number[][] = Array.from({ length: maxHatNumber + 1 }, () => []);
9  
10    // Populate the graph with the information about which people can wear which hats
11    for (let i = 0; i < numPeople; ++i) {
12        for (const hat of hats[i]) {
13            hatToPeopleGraph[hat].push(i);
14        }
15    }
16  
17    // DP array to store ways to distribute hats
18    // dp[hatNumber][mask] will represent the number of ways to distribute 
19    // the first hatNumber hats among people represented by mask
20    const dp: number[][] = Array.from({ length: maxHatNumber + 1 }, () =>
21        Array.from({ length: 1 << numPeople }, () => 0),
22    );
23  
24    // Base case: for 0 hats we have one way to assign - none to anyone
25    dp[0][0] = 1;
26  
27    // Modulus for the result to prevent integer overflow
28    const mod = 1e9 + 7;
29  
30    // Iterate over all hats
31    for (let hatNumber = 1; hatNumber <= maxHatNumber; ++hatNumber) {
32        // Iterate over all combinations of people
33        for (let mask = 0; mask < 1 << numPeople; ++mask) {
34            // The number of ways to distribute hats without considering the current hat
35            dp[hatNumber][mask] = dp[hatNumber - 1][mask];
36            // Iterate over all people that can wear the current hat
37            for (const person of hatToPeopleGraph[hatNumber]) {
38                // Check if the current person is included in the mask
39                if (((mask >> person) & 1) === 1) {
40                    // Add ways from the previous hat state excluding the current person
41                    dp[hatNumber][mask] = (dp[hatNumber][mask] + dp[hatNumber - 1][mask ^ (1 << person)]) % mod;
42                }
43            }
44        }
45    }
46  
47    // Return the number of ways to assign all hats to all people
48    // All people are represented by the mask (1 << numPeople) - 1, which has all bits set
49    return dp[maxHatNumber][(1 << numPeople) - 1];
50}
51
Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Time and Space Complexity

The provided code defines a function numberWays which calculates the number of ways people can wear hats given certain constraints. The analysis of its time and space complexity is as follows:

Time Complexity

The time complexity of the function is O(m * 2^n * n). Here's a breakdown of why that's the case:

  • m represents the maximum number of different hats, which can go up to 40 as per the problem constraints.
  • n is the number of people, limited to 10 in this scenario.
  • 2^n signifies the number of different states or combinations for the assignment of hats to the n people. Since each person can either wear a hat or not, there are 2^n possible states.

For each of the m hats, the algorithm iterates over all 2^n combinations, and for each combination, it can potentially iterate over all n people to update the state (f[i][j]). As a result, the time complexity amounts to the multiplicative product of these terms.

Space Complexity

The space complexity of the function is O(m * 2^n). This is due to the following reasons:

  • An m + 1 by 2^n sized 2D list f is created to store the states of hat assignments, where each sub-list f[i] has a length of 2^n to represent all combinations of n people, and there are m + 1 such sub-lists (ranging from 0 to m).
  • The additional data structures use negligible space compared to the size of f, so their contribution to space complexity is not considered dominant.

In summary, the algorithm requires a significant amount of space proportional to the number of hat combinations multiplied by the number of different hats.

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


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫