p80 — Number of Ways to Wear Different Hats

Source: LeetCode 1434 · Hard · Topics: Bitmask DP, Subject Flip Companies (2024–2025): Google (high), Amazon (high), Meta (medium-high), Microsoft (medium) Loop position: The bitmask-DP “flip the subject” trick. Naive bitmask on hats is 2^40 — infeasible. Flipping to bitmask on people (≤10 → 2^10 = 1024 states) makes it trivial. Tests whether the candidate sees the dimensional flip.

1. Quick Context

n people (≤ 10). 40 hats. hats[i] = list of hat ids person i likes. Each person wears exactly one hat; each hat worn by at most one person. Count ways to assign hats so everyone wears a hat they like. Modulo 10^9 + 7.

KEY: people ≤ 10 → bitmask on people (2^10 = 1024). Iterate hats (40) outer, people-masks inner, people who like current hat in innermost.

dp[h][mask] = number of ways using hats 1..h to satisfy exactly the people in mask. Transitions:

  • Skip hat h: dp[h][mask] += dp[h-1][mask].
  • Assign hat h to some person p who likes it AND p in mask: dp[h][mask] += dp[h-1][mask ^ (1<<p)].

Build liked_by[hat] = list of people who like that hat. O(40 · 1024 · 10) ≈ 410K ops.

Answer: dp[40][(1<<n) - 1] mod 1e9+7.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/

STOP. 45-min timer. The “flip subject” insight is the entire problem.

3. Prerequisite Concepts

  • Bitmask DP (LC 691, 698, 943).
  • “Subject flip” pattern: when one dimension is small (people = 10), iterate on the other (hats = 40) outer.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Count perfect assignments people→hats respecting preferences, distinct hats, mod 1e9+7.

2. Clarify: n ≤ 10? Yes (critical constraint). Hats numbered 1..40. Output mod 1e9+7.

3. Examples: hats=[[3,4],[4,5],[5]] → 1 (only assignment 3,4,5). hats=[[3,5,1],[3,5]] → 4.

5. Brute: Recursively assign person 0 a liked hat, mark used, recurse. Exponential in n (≤ 10! = 3.6M; tractable for n ≤ 10 but slower).

6. Target: O(40 · 2^n · n).

7. Pattern: Bitmask DP with subject flip.

8. Develop: see solution.py.

9. Test: single person; everyone likes same hat (→ multiple but each can wear one); n=10 random.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why naive “bitmask on hats” fails

Naive bitmask dp[hat_mask] = number of ways to assign hats marked in hat_mask to people. States: 2^40 = 1 trillion. Infeasible.

6.2 The flip: iterate over hats, bitmask on people

People = 10 → 2^10 = 1024 states. Iterate hats 1..40 outer (linear), people-mask inner (1024), people-who-like-this-hat innermost (≤10).

dp[h][mask] = number of ways using hats 1..h to satisfy exactly the people in mask.

6.3 Why iterate hats outer (not people outer)

If we iterate people outer (“for each person, assign a hat”), we’d need a hat-bitmask state to track usage → 2^40. Iterating hats outer lets us SKIP unused hats freely (each hat is “use or skip”); only need to track people satisfied so far.

6.4 Precompute liked_by[hat]

For each hat 1..40, list of people who like it. Built in O(sum of hats[i] sizes) one-pass.

6.5 Transitions (in code)

for h in 1..40:
    for mask in 0..(1<<n)-1:
        dp[h][mask] = dp[h-1][mask]   # skip hat h
        for p in liked_by[h]:
            if mask & (1<<p):
                dp[h][mask] = (dp[h][mask] + dp[h-1][mask ^ (1<<p)]) % MOD

6.6 1D rolling

dp[mask] only depends on dp[mask] (skip) and dp[mask ^ (1<<p)] (a subset of mask with one fewer bit). Iterate masks in any order if we use a fresh array per hat — or, since mask ^ (1<<p) has STRICTLY fewer bits than mask, iterate masks from high to low population… actually the safest is two-array.

6.7 General principle: “small-dimension subject flip”

When two dimensions exist (A small, B large), make B the outer loop variable and A the state. The state space is 2^|A|; the loop is |B|. Total O(|B| · 2^|A| · |A|).

Examples:

  • LC 943 Shortest Superstring: n ≤ 12 words; bitmask on words.
  • LC 691 Stickers to Spell Word: target ≤ 15 chars; bitmask on target chars.
  • LC 1601 Maximum Number of Achievable Transfer Requests: n ≤ 16 buildings; enumerate request-subsets.
  • LC 1986 Min Sessions: tasks ≤ 14; bitmask on tasks.

7. Anti-Pattern Analysis

  1. Bitmask on hats (2^40) — infeasible; classic mistake.
  2. Iterate people outer with bitmask on hats — same trap, different framing.
  3. Forget to mod — overflow on n=10 with many liked hats; answer wrong.
  4. Off-by-one on hat index — hats are 1..40, often easier to 0-index internally.
  5. Iterate the “people who like hat h” outer instead of inner — works but no speedup.
  6. Try meet-in-the-middle on hats — 2^20 × 2^20 still too much; the flip is cleaner.

8. Skills & Takeaways

  • Subject-flip insight on bitmask DP.
  • Per-element subset enumeration in O(2^k · k).
  • Modular arithmetic discipline.

9. When to Move On

  • Solve cold in 35 min with the flip articulated unprompted.
  • Cite at least 2 other “small-dimension flip” problems (943, 691).
  • Mod correctly; no overflow.

10. Company Context

  • Google: L5/L6; bitmask DP is a frequent probe.
  • Amazon: L6; assignment problems.
  • Meta: E5/E6; sometimes wrapped as scheduling.

Strong: “Identified the flip cold (n ≤ 10 → bitmask people, iterate hats outer), O(40 · 1024 · 10), cited family (Stickers, Superstring), correct mod.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
FlipNone (2^40)After hintCold+ cites general principle
Subject choiceWrongAfter hintRight cold+ proves bound
FamilyNoneNone1+ citesMultiple cites + Hungarian/assignment LP framing
ModForgetsAfter reviewCorrect+ frames as ring arithmetic

12. Level Delta

  • Mid (L4): Brute or wrong-bitmask; gets flipped DP after explicit hint.
  • Senior (L5): Flip cold; cites at least one similar problem; correct mod and complexity.
  • Staff (L6): + general “small-dimension flip” principle + cites 3+ similar problems + Hungarian algorithm comparison.
  • Principal (L7+): + assignment problem as LP + permanent of matrix = #perfect matchings = #P-hard in general (but tractable here because one side ≤ 10) + connection to inclusion-exclusion.

13. Follow-up Q&A

Q1: What if n = 30? A1: 2^30 = 1G states; infeasible. Switch to matching-based algorithm (bipartite #perfect-matchings via permanent — #P-hard in general; approximate with Ryser’s formula at 2^n · n).

Q2: What if hats = 1,000,000? A2: Only hats that are liked by SOMEONE matter; filter to active hats first. Active ≤ 10 · max_liked_per_person.

Q3: Maximize assignments instead of count? A3: Bipartite max matching (Hopcroft-Karp); polynomial.

Q4: Each person can wear multiple hats? A4: Reduces to “for each hat, independently pick a person who likes it or skip” → product across hats.

Q5: Min-cost assignment (weighted hats)? A5: Bipartite min-cost matching (Hungarian, O(n³) on small side).

14. Solution Walkthrough

See solution.py:

  • number_ways_dp — bottom-up O(40 · 2^n · n).
  • number_ways_memo — top-down @lru_cache on (hat, mask).
  • number_ways_brute — recursive assignment with used-hats set (oracle).

15. Beyond the Problem

Principal code review: “Number of Ways to Wear Different Hats is the canonical ‘subject-flip bitmask DP’. The insight — when two dimensions exist and one is small, flip which one becomes the state — is one of the most-leveraged tricks in competitive programming. The same principle drives: GPU kernels (iterate over the small dim outer, batch the large dim inner), database joins (build hash table on the smaller side, probe with the larger), and randomized algorithms (state-space pruning: small state ⇒ memoize, large state ⇒ Monte Carlo). At the Staff+ bar, frame this as: ‘the optimal subject of memoization is the dimension whose value space is exponential-but-small; the other dimension becomes a linear loop.’ Then connect to the deeper result: counting bipartite perfect matchings is #P-hard via matrix permanent, but tractable when one side is small — making this problem a tractable instance of an intractable general problem, which is exactly the kind of structural observation that distinguishes principal-level engineering judgment.”