1434. Number of Ways to Wear Different Hats to Each Other LeetCode Solution
In this guide, you will get 1434. Number of Ways to Wear Different Hats to Each Other LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Wear Different Hats to Each Other problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways to Wear Different Hats to Each Other
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 ith person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 109 + 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.
n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.
Complexity Analysis
Time Complexity: O(40 \cdot 2^n \cdot n), where n = |\texttt{hats}|
Space Complexity: O(40 \cdot 2^n)
1434. Number of Ways to Wear Different Hats to Each Other LeetCode Solution in C++
class Solution {
public:
int numberWays(vector<vector<int>>& hats) {
constexpr int nHats = 40;
const int nPeople = hats.size();
vector<vector<int>> hatToPeople(nHats + 1);
vector<vector<int>> mem(nHats + 1, vector<int>(1 << nPeople, -1));
for (int i = 0; i < nPeople; ++i)
for (const int hat : hats[i])
hatToPeople[hat].push_back(i);
return numberWays(hats, 0, 1, hatToPeople, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of ways to assign hats 1, 2, ..., h to people, where
// `assignment` is the bitmask of the current assignment.
int numberWays(const vector<vector<int>>& hats, int assignment, int h,
const vector<vector<int>>& hatToPeople,
vector<vector<int>>& mem) {
// All the people are assigned.
if (assignment == (1 << hats.size()) - 1)
return 1;
if (h > 40)
return 0;
if (mem[h][assignment] != -1)
return mem[h][assignment];
// Don't wear the hat `h`.
mem[h][assignment] = numberWays(hats, assignment, h + 1, hatToPeople, mem);
for (const int p : hatToPeople[h]) {
// The person `p` was assigned the hat `h` before.
if (assignment >> p & 1)
continue;
// Assign the hat `h` to the person `p`.
mem[h][assignment] +=
numberWays(hats, assignment | 1 << p, h + 1, hatToPeople, mem);
mem[h][assignment] %= kMod;
}
return mem[h][assignment];
}
}; /* code provided by PROGIEZ */
1434. Number of Ways to Wear Different Hats to Each Other LeetCode Solution in Java
class Solution {
public int numberWays(List<List<Integer>> hats) {
final int nHats = 40;
final int nPeople = hats.size();
List<Integer>[] hatToPeople = new List[nHats + 1];
Integer[][] mem = new Integer[nHats + 1][1 << nPeople];
for (int i = 1; i <= nHats; ++i)
hatToPeople[i] = new ArrayList<>();
for (int i = 0; i < nPeople; ++i)
for (final int hat : hats.get(i))
hatToPeople[hat].add(i);
return numberWays(hats, 0, 1, hatToPeople, mem);
}
private static final int kMod = 1_000_000_007;
// Returns the number of ways to assign hats 1, 2, ..., h to people, where
// `assignment` is the bitmask of the current assignment.
private int numberWays(List<List<Integer>> hats, int assignment, int h,
List<Integer>[] hatToPeople, Integer[][] mem) {
// All the people are assigned.
if (assignment == (1 << hats.size()) - 1)
return 1;
if (h > 40)
return 0;
if (mem[h][assignment] != null)
return mem[h][assignment];
// Don't wear the hat `h`.
int ans = numberWays(hats, assignment, h + 1, hatToPeople, mem);
for (final int p : hatToPeople[h]) {
// The person `p` was assigned the hat `h` before.
if ((assignment >> p & 1) == 1)
continue;
// Assign the hat `h` to the person `p`.
ans += numberWays(hats, assignment | 1 << p, h + 1, hatToPeople, mem);
ans %= kMod;
}
return mem[h][assignment] = ans;
}
} // code provided by PROGIEZ
1434. Number of Ways to Wear Different Hats to Each Other LeetCode Solution in Python
class Solution {
public:
int numberWays(vector<vector<int>>& hats) {
constexpr int kMod = 1'000'000'007;
constexpr int nHats = 40;
const int nPeople = hats.size();
const int nAssignments = 1 << nPeople;
vector<vector<int>> hatToPeople(nHats + 1);
// dp[i][j] := the number of ways to assign hats 1, 2, ..., i to people,
// where j is the bitmask of the current assignment
vector<vector<int>> dp(nHats + 1, vector<int>(nAssignments));
dp[0][0] = 1;
for (int i = 0; i < nPeople; ++i)
for (const int hat : hats[i])
hatToPeople[hat].push_back(i);
for (int h = 1; h <= nHats; ++h)
for (int j = 0; j < nAssignments; ++j) {
// We can cover the assignment j in 2 ways:
// 1. Assign the first h - 1 hats to people without using the hat `h`.
dp[h][j] += dp[h - 1][j];
dp[h][j] %= kMod;
for (const int p : hatToPeople[h])
if (j >> p & 1) {
// 2. Assign the first h - 1 hats to people without the person `p`
// and assign the hat `h` to the person `p`.
dp[h][j] += dp[h - 1][j ^ 1 << p];
dp[h][j] %= kMod;
}
}
return dp[nHats][nAssignments - 1];
}
}; # code by PROGIEZ
