Jobs

Interviews

Discussions

Number of Ways to Wear Different Hats to Each Other

Hard

Asked by:

15 views

Topics:

ArraysDynamic ProgrammingBit Manipulation

There are n people and 40 types of hats labeled from 1 to 40.

Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the i^th person.

Return the number of ways that n people can wear different hats from each other.

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

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats:
(3,5), (5,3), (1,3) and (1,5)

Example 3:

Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

Constraints:

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.

Try coding it in LeetCode

Number of Ways to Wear Different Hats to Each Other

Hard

Asked by:

15 views

Topics:

ArraysDynamic ProgrammingBit Manipulation

There are n people and 40 types of hats labeled from 1 to 40.

Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the i^th person.

Return the number of ways that n people can wear different hats from each other.

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

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats:
(3,5), (5,3), (1,3) and (1,5)

Example 3:

Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

Constraints:

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.

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 are the maximum values for the number of people (length of `hats`) and the number of hats each person likes (length of `hats[i]` for any i)?
Can a person have an empty list of hats they like (i.e., `hats[i]` is empty)? If so, how should I handle that?
Can multiple people like the same hat? If so, does that hat become unavailable to other people once assigned to one person?
If there is no way to assign hats such that everyone has a different hat, what value should I return?
Is the input guaranteed to be valid? For example, will there always be at least as many hats available in the combined lists as there are people?

Brute Force Solution

Approach

The core idea is to try every single possible combination of hats assigned to people. We'll go through each person one by one, assigning them a hat from their list of possible hats. We'll check if the current assignment is valid, and if so, move on to the next person.

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

Start with the first person.
Try giving them the first hat from their list of favorite hats.
Check if anyone else is already wearing that hat.
If nobody else is wearing that hat, move on to the second person.
For the second person, try giving them the first hat from their list of favorite hats that hasn't been used yet.
Keep checking if the current assignment results in two or more people wearing the same hat.
If there's a conflict (same hat), backtrack and try a different hat for the previous person.
If all people have been assigned different hats, increase the count of valid combinations by one.
Repeat this process, exploring all possible hat assignments until all options have been exhausted.
The final answer is the total count of valid combinations of hats.

Code Implementation

def number_ways(hats_for_person):
    number_of_people = len(hats_for_person)
    assigned_hats = [0] * number_of_people
    valid_combinations_count = 0

    def solve(person_index):
        nonlocal valid_combinations_count

        # Base case: All people have been assigned hats
        if person_index == number_of_people:
            valid_combinations_count += 1
            return

        # Iterate through each hat that the current person likes
        for hat in hats_for_person[person_index]:
            # Check if the hat is already being worn by someone else
            is_hat_available = True
            for previous_person in range(person_index):
                if assigned_hats[previous_person] == hat:
                    is_hat_available = False
                    break

            # If the hat is available, assign it to the current person
            if is_hat_available:
                assigned_hats[person_index] = hat
                # Recursively try to assign hats to the next person
                solve(person_index + 1)

                # Backtrack: Unassign the hat to explore other possibilities.
                assigned_hats[person_index] = 0

    solve(0)
    return valid_combinations_count

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores all possible hat assignments to people using backtracking. In the worst-case scenario, each person could have multiple hat choices, leading to a combinatorial explosion. For n people, the number of possible assignments can approach n! (n factorial) in the worst-case if each person has many hat choices and we need to explore almost all permutations before finding valid solutions. The algorithm effectively generates and checks (potentially) all permutations of hat assignments before settling on valid combinations. Therefore the time complexity is O(n!).

Space Complexity

O(N) – The plain English explanation describes a recursive backtracking process where we assign hats to people one by one. In the worst case, the recursion depth can reach N, where N is the number of people. Each level of recursion requires storing information like the current hat assignments (whether a hat is used or not). This leads to a call stack that can grow up to a depth of N. Therefore the space complexity is O(N) primarily due to the recursion stack.

Optimal Solution

Approach

This problem asks us to count the number of ways people can wear hats, given each person has a list of hats they can wear. The trick is to use a counting method based on who is wearing a hat, instead of which hat is being worn, to drastically reduce the workload.

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

Picture the problem as assigning hats to people one by one, rather than figuring out who wears which hat.
Start with the first person and consider all the hats they can wear.
For each hat that the first person can wear, consider the options for the second person, remembering they can't wear the same hat.
Keep track of the number of ways each person can be assigned a hat, building upon the previous person's options.
To avoid recalculating the same scenarios, remember counts of partial hat assignments using a technique to store and reuse these values.
Continue this process until every person has a hat assigned to them, then add that to the total number of ways.
Since the numbers can get big, remember to take the result modulo a provided number to avoid exceeding storage capacity.

Code Implementation

def number_of_ways_to_wear_hats(hats_for_person):
    number_of_people = len(hats_for_person)
    MOD = 10**9 + 7

    hat_to_people = [[] for _ in range(41)]
    for person_index, hats in enumerate(hats_for_person):
        for hat in hats:
            hat_to_people[hat].append(person_index)

    # dp[mask] is the number of ways to assign hats to the people represented by the mask.
    dp = [0] * (1 << number_of_people)
    dp[0] = 1

    for hat_index in range(1, 41):
        next_dp = dp[:]

        # Iterate through all possible assignment states.
        for mask in range(1 << number_of_people):
            # Consider each person who can wear the current hat.
            for person_index in hat_to_people[hat_index]:
                # If the person is not wearing a hat yet.
                if not (mask & (1 << person_index)):
                    # Calculate the new mask.
                    new_mask = mask | (1 << person_index)
                    # Update the dp table.
                    next_dp[new_mask] = (next_dp[new_mask] + dp[mask]) % MOD

        # Update dp for the next iteration.
        dp = next_dp

    # The result is the number of ways to assign hats to all people.
    return dp[(1 << number_of_people) - 1]

Big(O) Analysis

Time Complexity

O(2^n * n) – The algorithm considers assigning hats to people one by one. The state is represented by a bitmask indicating which people have been assigned hats, and the last person assigned. There are 2^n possible bitmasks (representing all combinations of people wearing hats) and for each of those, we iterate through the hats available to the next unassigned person, which can be at most n (or a function of the number of hats). The memoization avoids recomputing subproblems, but the exploration space is still exponential in the number of people. For each state, finding the next unassigned person takes O(n), leading to an overall time complexity of O(2^n * n).

Space Complexity

O(2^N) – The primary space complexity comes from storing intermediate counts of partial hat assignments. Step 5 mentions remembering counts of partial hat assignments, which suggests a memoization technique, most likely implemented using a 2D array or hash map. In the worst-case, this memoization table needs to store the number of ways to assign hats for every possible subset of people (2^N subsets) and the current hat being considered (up to N hats). Therefore, the space used by the memoization table is proportional to 2^N * N. However, since only the number of people (N) is given and hat count is unknown, it's reasonable to assume the upper bound is driven by the number of possible subsets for people only, giving O(2^N) space.

Edge Cases

Case	How to Handle
Empty hats array	Return 0 because there are no possible arrangements if no one has any hats.
One person, with one or more hats	Return 1 because there's only one way for that person to wear a hat.
Many people, but some people have no hats	Return 0 because those people cannot wear a hat, making a valid arrangement impossible.
All people like the same set of hats	The number of ways to assign hats might be fewer than the number of permutations because the set is fixed.
Number of people is greater than the number of distinct hats	Return 0 because it's impossible to assign different hats to each person.
Hat list for each person has duplicate hat numbers	The duplicates will be treated as one unique hat for that person, so no special handling is needed.
The recursive calls create a large call stack that can cause stack overflow	Use dynamic programming (memoization) to store computed results to avoid recalculating and reduce recursion depth.
Integer overflow when calculating the number of ways	Take the modulo (10^9 + 7) after each multiplication or addition to prevent integer overflow.

Empty hats array

How to Handle:

Return 0 because there are no possible arrangements if no one has any hats.

One person, with one or more hats

How to Handle:

Return 1 because there's only one way for that person to wear a hat.

Many people, but some people have no hats

How to Handle:

Return 0 because those people cannot wear a hat, making a valid arrangement impossible.

All people like the same set of hats

How to Handle:

The number of ways to assign hats might be fewer than the number of permutations because the set is fixed.

Number of people is greater than the number of distinct hats

How to Handle:

Return 0 because it's impossible to assign different hats to each person.

Hat list for each person has duplicate hat numbers

How to Handle:

The duplicates will be treated as one unique hat for that person, so no special handling is needed.

The recursive calls create a large call stack that can cause stack overflow

How to Handle:

Use dynamic programming (memoization) to store computed results to avoid recalculating and reduce recursion depth.

Integer overflow when calculating the number of ways

How to Handle:

Take the modulo (10^9 + 7) after each multiplication or addition to prevent integer overflow.

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 are the maximum values for the number of people (length of `hats`) and the number of hats each person likes (length of `hats[i]` for any i)?
Can a person have an empty list of hats they like (i.e., `hats[i]` is empty)? If so, how should I handle that?
Can multiple people like the same hat? If so, does that hat become unavailable to other people once assigned to one person?
If there is no way to assign hats such that everyone has a different hat, what value should I return?
Is the input guaranteed to be valid? For example, will there always be at least as many hats available in the combined lists as there are people?

Brute Force Solution

Approach

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

Start with the first person.
Try giving them the first hat from their list of favorite hats.
Check if anyone else is already wearing that hat.
If nobody else is wearing that hat, move on to the second person.
For the second person, try giving them the first hat from their list of favorite hats that hasn't been used yet.
Keep checking if the current assignment results in two or more people wearing the same hat.
If there's a conflict (same hat), backtrack and try a different hat for the previous person.
If all people have been assigned different hats, increase the count of valid combinations by one.
Repeat this process, exploring all possible hat assignments until all options have been exhausted.
The final answer is the total count of valid combinations of hats.

Code Implementation

def number_ways(hats_for_person):
    number_of_people = len(hats_for_person)
    assigned_hats = [0] * number_of_people
    valid_combinations_count = 0

    def solve(person_index):
        nonlocal valid_combinations_count

        # Base case: All people have been assigned hats
        if person_index == number_of_people:
            valid_combinations_count += 1
            return

        # Iterate through each hat that the current person likes
        for hat in hats_for_person[person_index]:
            # Check if the hat is already being worn by someone else
            is_hat_available = True
            for previous_person in range(person_index):
                if assigned_hats[previous_person] == hat:
                    is_hat_available = False
                    break

            # If the hat is available, assign it to the current person
            if is_hat_available:
                assigned_hats[person_index] = hat
                # Recursively try to assign hats to the next person
                solve(person_index + 1)

                # Backtrack: Unassign the hat to explore other possibilities.
                assigned_hats[person_index] = 0

    solve(0)
    return valid_combinations_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Picture the problem as assigning hats to people one by one, rather than figuring out who wears which hat.
Start with the first person and consider all the hats they can wear.
For each hat that the first person can wear, consider the options for the second person, remembering they can't wear the same hat.
Keep track of the number of ways each person can be assigned a hat, building upon the previous person's options.
To avoid recalculating the same scenarios, remember counts of partial hat assignments using a technique to store and reuse these values.
Continue this process until every person has a hat assigned to them, then add that to the total number of ways.
Since the numbers can get big, remember to take the result modulo a provided number to avoid exceeding storage capacity.

Code Implementation

def number_of_ways_to_wear_hats(hats_for_person):
    number_of_people = len(hats_for_person)
    MOD = 10**9 + 7

    hat_to_people = [[] for _ in range(41)]
    for person_index, hats in enumerate(hats_for_person):
        for hat in hats:
            hat_to_people[hat].append(person_index)

    # dp[mask] is the number of ways to assign hats to the people represented by the mask.
    dp = [0] * (1 << number_of_people)
    dp[0] = 1

    for hat_index in range(1, 41):
        next_dp = dp[:]

        # Iterate through all possible assignment states.
        for mask in range(1 << number_of_people):
            # Consider each person who can wear the current hat.
            for person_index in hat_to_people[hat_index]:
                # If the person is not wearing a hat yet.
                if not (mask & (1 << person_index)):
                    # Calculate the new mask.
                    new_mask = mask | (1 << person_index)
                    # Update the dp table.
                    next_dp[new_mask] = (next_dp[new_mask] + dp[mask]) % MOD

        # Update dp for the next iteration.
        dp = next_dp

    # The result is the number of ways to assign hats to all people.
    return dp[(1 << number_of_people) - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty hats array	Return 0 because there are no possible arrangements if no one has any hats.
One person, with one or more hats	Return 1 because there's only one way for that person to wear a hat.
Many people, but some people have no hats	Return 0 because those people cannot wear a hat, making a valid arrangement impossible.
All people like the same set of hats	The number of ways to assign hats might be fewer than the number of permutations because the set is fixed.
Number of people is greater than the number of distinct hats	Return 0 because it's impossible to assign different hats to each person.
Hat list for each person has duplicate hat numbers	The duplicates will be treated as one unique hat for that person, so no special handling is needed.
The recursive calls create a large call stack that can cause stack overflow	Use dynamic programming (memoization) to store computed results to avoid recalculating and reduce recursion depth.
Integer overflow when calculating the number of ways	Take the modulo (10^9 + 7) after each multiplication or addition to prevent integer overflow.

Empty hats array

How to Handle:

Return 0 because there are no possible arrangements if no one has any hats.

One person, with one or more hats

How to Handle:

Return 1 because there's only one way for that person to wear a hat.

Many people, but some people have no hats

How to Handle:

Return 0 because those people cannot wear a hat, making a valid arrangement impossible.

All people like the same set of hats

How to Handle:

The number of ways to assign hats might be fewer than the number of permutations because the set is fixed.

Number of people is greater than the number of distinct hats

How to Handle:

Return 0 because it's impossible to assign different hats to each person.

Hat list for each person has duplicate hat numbers

How to Handle:

The duplicates will be treated as one unique hat for that person, so no special handling is needed.

The recursive calls create a large call stack that can cause stack overflow

How to Handle:

Use dynamic programming (memoization) to store computed results to avoid recalculating and reduce recursion depth.

Integer overflow when calculating the number of ways

How to Handle:

Take the modulo (10^9 + 7) after each multiplication or addition to prevent integer overflow.