Number of Ways to Wear Different Hats to Each Other
HardPrompt
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 n people can wear different hats from 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.
Constraints:
n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i]contains a list of unique integers.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a standard backtracking algorithm to explore all possible ways of assigning hats to people. We try to assign a hat to each person one by one, from person 0 to person n-1. For each person, we iterate through their list of preferred hats. If a hat is not already worn by someone else, we assign it to the current person and recursively move on to the next person. If we successfully assign hats to all n people, we count it as one valid way.
Algorithm
- Define a recursive function, say
solve(personIndex, usedHatsMask), which calculates the number of ways to assign hats to people frompersonIndexton-1, given that the hats represented byusedHatsMaskare already taken. - Base Case: If
personIndexequalsn, it means we have successfully assigned a unique hat to allnpeople. Return 1, as this represents one valid assignment. - Recursive Step: For the current
personIndex, iterate through all the hatshthat this person prefers (fromhats[personIndex]). - For each preferred hat
h, check if it has already been used by examining theh-th bit inusedHatsMask. - If the hat
his not used, make a recursive call:solve(personIndex + 1, usedHatsMask | (1 << h)). This explores assigning hathto the current person and moving to the next person. - Sum the results from all valid recursive calls to get the total number of ways for the current state.
- The initial call to the function would be
solve(0, 0).
Walkthrough
The core idea is to build a valid assignment person by person. We maintain the state using two parameters: the index of the person we are currently considering (personIndex) and a bitmask (usedHatsMask) to keep track of which hats have already been assigned. The recursion explores every possible branch of assignments. While simple to conceptualize, this method suffers from a massive number of redundant computations and an explosive number of states. For example, the arrangement of hats for the first k people will be recomputed for every different arrangement of hats for the people before them. Due to the constraints (n up to 10, hats up to 40), the number of paths to explore is prohibitively large, leading to a 'Time Limit Exceeded' error on most platforms.
Complexity
Time
O(n! * C)
Space
O(n + num_hats)
Trade-offs
Pros
Simple to understand and conceptualize.
Cons
Extremely inefficient and will time out for the given constraints.
The state space for memoization
(person, used_hats_mask)would ben * 2^40, which is too large to fit in memory, preventing a straightforward DP optimization of this approach.
This approach uses dynamic programming with memoization to solve the problem efficiently. The crucial observation is that the state space becomes manageable if we iterate through the hats instead of the people. The state of our DP is defined by (hatId, personMask), which represents the number of ways to assign hats from hatId to 40 to a specific subset of people who are not yet covered by the personMask.
By processing hats one by one, we decide for each hat whether to assign it to an eligible person or to skip it. This avoids the large state space issue of the brute-force approach and effectively solves the problem within the time limits.
Algorithm
- Preprocessing: The key insight is to change the perspective from assigning hats to people to assigning people to hats. Create a mapping from each hat ID to a list of people who prefer that hat. Let's call this
peopleByHat. - DP State: Define a recursive function
solve(hatId, personMask)with memoization.hatIdis the current hat we are considering (from 1 to 40), andpersonMaskis a bitmask representing the set of people who have already been assigned a hat. - Memoization: Use a 2D array,
dp[hatId][personMask], to store the results of subproblems to avoid re-computation. - Base Cases:
- If
personMaskindicates all people have a hat (personMask == (1 << n) - 1), we have found a valid assignment. Return 1. - If
hatIdexceeds 40 and not all people have hats, it's impossible to complete the assignment. Return 0.
- If
- Recursive Step: For the state
(hatId, personMask), we have two choices forhatId:- Don't use
hatId: The number of ways issolve(hatId + 1, personMask). - Use
hatId: Iterate through the list of peoplepwho preferhatId(frompeopleByHat[hatId]). If personphas not yet been assigned a hat (i.e., thep-th bit inpersonMaskis 0), we can assignhatIdto them. The number of ways for this choice issolve(hatId + 1, personMask | (1 << p)). Sum these up for all such peoplep.
- Don't use
- The total ways for the current state is the sum of ways from both choices. Store this result in
dp[hatId][personMask]before returning.
Walkthrough
First, we preprocess the input hats list to create an inverted index, peopleByHat, where peopleByHat[h] contains a list of people who like hat h. This makes it easy to find candidates for each hat.
We then define a recursive function solve(hatId, mask) that computes the number of ways to assign hats from hatId onwards, given that the people represented by mask have already been assigned hats. The results are stored in a dp table to avoid recomputing for the same state (hatId, mask).
The recursion explores two main possibilities for each hat: either we don't use it and move to the next hat, or we assign it to one of the people who prefer it and don't have a hat yet. The final answer is the result of the initial call solve(1, 0).
class Solution { int MOD = 1_000_000_007; List<Integer>[] peopleByHat; int n; int allMask; Integer[][] dp; public int numberWays(List<List<Integer>> hats) { this.n = hats.size(); this.allMask = (1 << n) - 1; this.peopleByHat = new ArrayList[41]; for (int i = 0; i <= 40; i++) { peopleByHat[i] = new ArrayList<>(); } for (int i = 0; i < n; i++) { for (int hat : hats.get(i)) { peopleByHat[hat].add(i); } } this.dp = new Integer[41][1 << n]; return solve(1, 0); } private int solve(int hatId, int mask) { if (mask == allMask) { return 1; } if (hatId > 40) { return 0; } if (dp[hatId][mask] != null) { return dp[hatId][mask]; } // Option 1: Don't use the current hat long ways = solve(hatId + 1, mask); // Option 2: Use the current hat for an eligible person for (int person : peopleByHat[hatId]) { if ((mask & (1 << person)) == 0) { ways = (ways + solve(hatId + 1, mask | (1 << person))) % MOD; } } return dp[hatId][mask] = (int) ways; }}Complexity
Time
O(num_hats * 2^n * n)
Space
O(num_hats * 2^n)
Trade-offs
Pros
Efficient enough to pass the given constraints.
Systematically avoids re-computation of subproblems through memoization.
Cons
Requires a significant amount of memory for the DP table,
O(num_hats * 2^n).
This approach is a space-optimized version of the hat-centric dynamic programming solution. Instead of using a 2D DP table, we use a 1D array of size 2^n. The state dp[mask] represents the number of ways to assign hats to the people represented by mask using the hats considered so far.
We iterate through each hat from 1 to 40. For each hat, we update the dp array based on the possibilities this new hat introduces. By iterating through the masks in a specific order (from largest to smallest), we can perform the updates in-place, effectively reducing the space complexity from O(num_hats * 2^n) to O(2^n) while keeping the time complexity the same.
Algorithm
- Preprocessing: As with the top-down approach, create the
peopleByHatmapping. - DP State: Use a 1D array
dpof size2^n.dp[mask]will store the number of ways to assign hats (up to the one currently being processed) to the set of people represented bymask. - Initialization: Initialize
dp[0] = 1, signifying one way to assign hats to zero people (by doing nothing). All otherdpentries are 0. - Iteration: Iterate through each hat
hfrom 1 to 40. - For each hat, we update the
dparray. To do this correctly in-place, we iterate through the masksmfrom(1 << n) - 1down to 0. - Transition: For each mask
m, we consider assigning the current hathto any eligible personpwithin that mask. An eligible personpis one who prefers hathand is represented in the maskm. - If person
pis in maskm, it means we can form the assignment formby giving hathtop, and having the remaining people (mwithoutp, i.e.,m ^ (1 << p)) assigned hats from the previous set (1 toh-1). - The number of ways to do this is
dp[m ^ (1 << p)]. We add this todp[m]. The update rule isdp[m] = (dp[m] + dp[m ^ (1 << p)]) % MOD. - The reverse iteration over masks is crucial. It ensures that when we compute
dp[m], the valuedp[m ^ (1 << p)](wherem ^ (1 << p) < m) is from the previous state (before considering hath). - Result: After iterating through all 40 hats, the final answer is
dp[(1 << n) - 1], which represents the number of ways to assign hats to allnpeople.
Walkthrough
The bottom-up approach builds the solution iteratively. We start with a dp array where dp[0] = 1 and all other dp[mask] = 0. This represents the base case: with zero hats, there's one way to cover zero people.
We then loop through each hat h from 1 to 40. In each iteration, we calculate the new dp states after considering hat h. The new value for dp[mask] is the old dp[mask] (representing ways without using hat h) plus the sum of ways for states where hat h is assigned to a person in the mask. Specifically, for each person p in mask who likes hat h, we add dp[mask ^ (1 << p)] to dp[mask]. This dp[mask ^ (1 << p)] represents the number of ways the smaller group of people could be formed with previous hats.
To perform this update using a single dp array, we iterate the masks in reverse. This ensures that when we calculate dp[mask], the values for smaller masks dp[mask ^ (1 << p)] have not yet been updated for the current hat h, so they correctly reflect the state from the previous iteration (h-1).
class Solution { int MOD = 1_000_000_007; public int numberWays(List<List<Integer>> hats) { int n = hats.size(); List<Integer>[] peopleByHat = new ArrayList[41]; for (int i = 0; i <= 40; i++) { peopleByHat[i] = new ArrayList<>(); } for (int i = 0; i < n; i++) { for (int hat : hats.get(i)) { peopleByHat[hat].add(i); } } int[] dp = new int[1 << n]; dp[0] = 1; for (int h = 1; h <= 40; h++) { for (int mask = (1 << n) - 1; mask >= 0; mask--) { for (int person : peopleByHat[h]) { if ((mask & (1 << person)) != 0) { int prevMask = mask ^ (1 << person); dp[mask] = (dp[mask] + dp[prevMask]) % MOD; } } } } return dp[(1 << n) - 1]; }}Complexity
Time
O(num_hats * 2^n * n)
Space
O(2^n)
Trade-offs
Pros
Most memory-efficient solution.
Iterative nature can sometimes have less overhead than recursion.
Same time efficiency as the top-down DP approach.
Cons
The logic for the in-place update (iterating masks in reverse) can be less intuitive than a top-down recursive approach.
Solutions
Solution
class Solution {public int numberWays(List<List<Integer>> hats) { int n = hats.size(); int m = 0; for (var h : hats) { for (int v : h) { m = Math.max(m, v); } } List<Integer>[] g = new List[m + 1]; Arrays.setAll(g, k->new ArrayList<>()); for (int i = 0; i < n; ++i) { for (int v : hats.get(i)) { g[v].add(i); } } final int mod = (int)1 e9 + 7; int[][] f = new int[m + 1][1 << n]; f[0][0] = 1; for (int i = 1; i <= m; ++i) { for (int j = 0; j < 1 << n; ++j) { f[i][j] = f[i - 1][j]; for (int k : g[i]) { if ((j >> k & 1) == 1) { f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod; } } } } return f[m][(1 << n) - 1]; }}class Solution {public: int numberWays(vector<vector<int>> &hats) { int n = hats.size(); int m = 0; for (auto &h : hats) { m = max(m, *max_element(h.begin(), h.end())); } vector<vector<int>> g(m + 1); for (int i = 0; i < n; ++i) { for (int &v : hats[i]) { g[v].push_back(i); } } const int mod = 1e9 + 7; int f[m + 1][1 << n]; memset(f, 0, sizeof(f)); f[0][0] = 1; for (int i = 1; i <= m; ++i) { for (int j = 0; j < 1 << n; ++j) { f[i][j] = f[i - 1][j]; for (int k : g[i]) { if (j >> k & 1) { f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod; } } } } return f[m][(1 << n) - 1]; }};class Solution: def numberWays(self, hats: List[List[int]]) -> int: g = defaultdict(list) for i, h in enumerate(hats): for v in h: g[v]. append(i) mod = 10 ** 9 + 7 n = len(hats) m = max(max(h) for h in hats) f = [[0] * (1 << n) for _ in range(m + 1)] f[0][0] = 1 for i in range(1, m + 1): for j in range(1 << n): f[i][j] = f[i - 1][j] for k in g[i]: if j >> k & 1: f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod return f[m][- 1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.