Hard

Quiz

#1434 Number of Ways to Wear Different Hats to Each Other

APPROACH

A group of n people must each be assigned a unique hat from a collection of 40 hat types (numbered 1 to 40). You are given a 2D array hats where hats[i] lists the hat types preferred by person i.

Count the total number of valid assignments in which every person receives a different hat, and return the result 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 chooses hat 3, Second person chooses 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.

1 of 4

1:00

What is the optimal approach for this problem?