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

Problem Explanation

Each person has a preference of hats that they can wear. However, no two persons can wear the same hat. The problem is asking for the number of permutations or the number of ways in which the hats can be distributed among the persons such that each person is wearing a hat that is in their preference list and no two persons are wearing the same hat.

Let's go through an example:

hats = [[3,5,1],[3,5]]

The possible solutions are (3,5), (5,3), (1,3), and (1,5). The first person can either wear 3, 5, or 1 and for each preference of the first person, the second person has at least one other preference. Hence, there are 4 possible ways the hats can be distributed among the two persons.

Approach

We can solve this problem by using dynamic programming. Each state of the DP is composed of two parts:

1. The current hat under consideration
2. The persons who have already been assigned a hat

The first step is to map each hat to the list of persons who have it in their preference. Then, the DP state can be represented by a bit-mask where if the i-th bit is set, it means the i-th person is wearing a hat. For each hat h, we can calculate the number of ways in which the persons can be assigned a hat. Initially, the number of ways is the same as the number of ways of assigning the hat h+1 to the persons. Then, for each person who prefers hat h, if that person is not already wearing a hat, we add the number of ways of assigning the hat h+1 to the remaining persons.

Solution in Python

1
2python
3class Solution:
4  def numberWays(self, hats):
5    # Total number of hats
6    hatNum = 40
7    # Number of people
8    peopleNum = len(hats)
9    # Map of hat to people who prefer it
10    hatToPeople = [[] for _ in range(hatNum + 1)]
11    for i in range(peopleNum):
12      for j in hats[i]:
13        hatToPeople[j].append(i)
14    # DP table
15    dp = [[0 for _ in range(1 << peopleNum)] for _ in range(hatNum + 1)]
16    dp[0][0] = 1
17    MOD = 10**9 + 7
18    for i in range(1, hatNum + 1):
19      dp[i] = dp[i - 1][:]
20      for j in hatToPeople[i]:
21        for k in range(1 << peopleNum):
22          if k & (1 << j):
23            dp[i][k] = (dp[i][k] + dp[i - 1][k ^ (1 << j)]) % MOD
24    return dp[hatNum][(1 << peopleNum) - 1]

Here, we first create a mapping from each hat to the lst of people who like that hat. Then, we initialize a DP Table where dp[i][j] represents the number of ways to assign the first i hats to the people bitmask j. For each hat and each person who likes that hat, we update the number of ways in the DP table. Finally, we return the number of ways to assign all hats to all people.## Solution in JavaScript

The JavaScript solution uses the same approach as the Python solution with the difference being in the implementation details due to the language difference.

Here it is:

1
2javascript
3var numberWays = function(hats) {
4    const hatNum = 40;
5    const peopleNum = hats.length;
6    const hatToPeople = Array(hatNum + 1).fill().map(() => []);
7    for(let i = 0; i < peopleNum; i++) {
8        for(let j of hats[i]) {
9            hatToPeople[j].push(i);
10        }
11    }
12
13    const MOD = 10**9 + 7;
14    const dp = Array(hatNum + 1).fill().map(() => Array(1 << peopleNum).fill(0));
15
16    dp[0][0] = 1;
17    for(let i = 1; i <= hatNum; i++) {
18        dp[i] = [...dp[i - 1]];
19        for(let j of hatToPeople[i]) {
20            for(let k = 0; k < (1 << peopleNum); k++) {
21                if((k & (1 << j)) !== 0) {
22                    dp[i][k] = (dp[i][k] + dp[i - 1][k ^ (1 << j)]) % MOD;
23                }
24            }
25        }
26    }
27    return dp[hatNum][(1 << peopleNum) - 1];
28};

Same as the Python solution, we first map each hat to the list of people who like that hat. Then, we create a DP table where dp[i][j] represents the number of ways to assign the first i hats to the people bitmask j. For each hat and each person who likes that hat, we update the number of ways in the DP table. At the end we return the number of ways to assign all hats to all people.

Solution in Java

The Java solution uses the same logic as the Python and JavaScript solutions. Here is the code:

1
2java
3class Solution {
4  public int numberWays(List<List<Integer>> hats) {
5    int n = hats.size();
6    int mod = 1_000_000_007;
7    int maxHats = 40;
8    
9    List<Integer>[] hatToPeople = new List[maxHats + 1];
10    for (int i = 0; i <= maxHats; i++)
11      hatToPeople[i] = new ArrayList<>();
12    
13    for (int i = 0; i < n; i++)
14      for (int hat: hats.get(i))
15        hatToPeople[hat].add(i);
16
17    int[][] dp = new int[maxHats + 1][1 << n];
18    dp[0][0] = 1;
19    for (int i = 1; i <= maxHats; i++) {
20      System.arraycopy(dp[i - 1], 0, dp[i], 0, 1 << n);
21      for (int person: hatToPeople[i]) {
22        for (int j = 0; j < 1 << n; j++) {
23          if ((j & (1 << person)) > 0) {
24            dp[i][j] = (dp[i][j] + dp[i - 1][j ^ (1 << person)]) % mod;
25          }
26        }
27      }
28    }
29    return dp[maxHats][(1 << n) - 1];
30  }
31}

With the above Java code, we've implemented the same logic just like we did in Python & JavaScript solution. We are creating a mapping of hats -> people who likes, and using that map we are populating the DP table for providing the number of ways to distribute the hats. Finally, we return the number of ways to assign all hats.