Problem#
At a popular bar, each customer has a set of favorite drinks, and will happily accept any drink among this set. For example, in the following situation, customer 0 will be satisfied with drinks 0, 1, 3, or 6.
A lazy bartender working at this bar is trying to reduce his effort by limiting the drink recipes he must memorize. Given a dictionary input such as the one above, return the fewest number of drinks he must learn in order to satisfy all customers.
Examples#
Example 1#
1
2
3
Input: { 0 : [ 0 , 1 , 3 , 6 ], 1 : [ 1 , 4 , 7 ], 2 : [ 2 , 4 , 7 , 5 ], 3 : [ 3 , 2 , 5 ], 4 : [ 5 , 8 ]}
Output: 2
Explanation: Drinks 1 and 5 will satisfy everyone. Customer 0 gets drink 1 , customers 1 and 2 can get drinks 1 or 5 , customer 3 gets drink 5 , and customer 4 gets drink 5.
Example 2#
1
2
3
Input: { 0 : [ 1 , 2 ], 1 : [ 2 , 3 ], 2 : [ 3 , 4 ]}
Output: 2
Explanation: We need drinks 2 and 3. Customer 0 gets drink 2 , customer 1 can get drink 2 or 3 , and customer 2 gets drink 3.
Example 3#
1
2
3
Input: { 0 : [ 1 ], 1 : [ 2 ], 2 : [ 3 ]}
Output: 3
Explanation: Each customer has only one preferred drink, so we need all three drinks: 1 , 2 , and 3.
Example 4#
1
2
3
Input: { 0 : [ 1 , 2 , 3 ], 1 : [ 1 , 2 , 3 ], 2 : [ 1 , 2 , 3 ]}
Output: 1
Explanation: All customers like the same drinks, so we only need one drink ( e. g ., drink 1 ) to satisfy everyone.
Example 5#
1
2
3
Input: {}
Output: 0
Explanation: No customers means no drinks needed.
Solution#
Method 1 - Greedy Set Cover#
Intuition#
This is a classic set cover problem where we want to find the minimum number of drinks (sets) that cover all customers. We can use a greedy approach: repeatedly choose the drink that satisfies the most unsatisfied customers until all customers are covered.
Approach#
Create a mapping of drinks to the customers they satisfy
Keep track of unsatisfied customers
Greedily select the drink that covers the most remaining customers
Remove satisfied customers from the unsatisfied set
Repeat until all customers are satisfied
Return the count of selected drinks
Code#
Cpp
Go
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public :
int minDrinks(unordered_map< int , vector< int >>& preferences) {
if (preferences.empty()) return 0 ;
// Build drink to customers mapping
< int , vector< int >> drinkToCustomers;
unordered_set< int > allCustomers;
for (auto & [customer, drinks] : preferences) {
allCustomers.insert(customer);
for (int drink : drinks) {
drinkToCustomers[drink].push_back(customer);
}
}
unordered_set< int > unsatisfied = allCustomers;
int drinkCount = 0 ;
while (! unsatisfied.empty()) {
// Find drink that covers most unsatisfied customers
int bestDrink = - 1 ;
int maxCovered = 0 ;
for (auto & [drink, customers] : drinkToCustomers) {
int covered = 0 ;
for (int customer : customers) {
if (unsatisfied.count(customer)) {
covered++ ;
}
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
// Remove satisfied customers
if (bestDrink != - 1 ) {
for (int customer : drinkToCustomers[bestDrink]) {
unsatisfied.erase(customer);
}
drinkCount++ ;
}
}
return drinkCount;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func minDrinks (preferences map [int ][]int ) int {
if len(preferences ) == 0 {
return 0
}
// Build drink to customers mapping
drinkToCustomers := make(map [int ][]int )
allCustomers := make(map [int ]bool )
for customer , drinks := range preferences {
allCustomers [customer ] = true
for _ , drink := range drinks {
drinkToCustomers [drink ] = append(drinkToCustomers [drink ], customer )
}
}
unsatisfied := make(map [int ]bool )
for customer := range allCustomers {
unsatisfied [customer ] = true
}
drinkCount := 0
for len(unsatisfied ) > 0 {
// Find drink that covers most unsatisfied customers
bestDrink := - 1
maxCovered := 0
for drink , customers := range drinkToCustomers {
covered := 0
for _ , customer := range customers {
if unsatisfied [customer ] {
covered ++
}
}
if covered > maxCovered {
maxCovered = covered
bestDrink = drink
}
}
// Remove satisfied customers
if bestDrink != - 1 {
for _ , customer := range drinkToCustomers [bestDrink ] {
delete(unsatisfied , customer )
}
drinkCount ++
}
}
return drinkCount
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public int minDrinks (Map< Integer, List< Integer>> preferences) {
if (preferences.isEmpty ()) return 0;
// Build drink to customers mapping
Map< Integer, List< Integer>> drinkToCustomers = new HashMap<> ();
Set< Integer> allCustomers = new HashSet<> ();
for (Map.Entry < Integer, List< Integer>> entry : preferences.entrySet ()) {
int customer = entry.getKey ();
allCustomers.add (customer);
for (int drink : entry.getValue ()) {
drinkToCustomers.computeIfAbsent (drink, k -> new ArrayList<> ()).add (customer);
}
}
Set< Integer> unsatisfied = new HashSet<> (allCustomers);
int drinkCount = 0;
while (! unsatisfied.isEmpty ()) {
// Find drink that covers most unsatisfied customers
int bestDrink = - 1;
int maxCovered = 0;
for (Map.Entry < Integer, List< Integer>> entry : drinkToCustomers.entrySet ()) {
int drink = entry.getKey ();
List< Integer> customers = entry.getValue ();
int covered = 0;
for (int customer : customers) {
if (unsatisfied.contains (customer)) {
covered++ ;
}
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
// Remove satisfied customers
if (bestDrink != - 1) {
for (int customer : drinkToCustomers.get (bestDrink)) {
unsatisfied.remove (customer);
}
drinkCount++ ;
}
}
return drinkCount;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution :
def min_drinks (self, preferences: Dict[int, List[int]]) -> int:
if not preferences:
return 0
# Build drink to customers mapping
drink_to_customers = {}
all_customers = set(preferences. keys())
for customer, drinks in preferences. items():
for drink in drinks:
if drink not in drink_to_customers:
drink_to_customers[drink] = []
drink_to_customers[drink]. append(customer)
unsatisfied = set(all_customers)
drink_count = 0
while unsatisfied:
# Find drink that covers most unsatisfied customers
best_drink = - 1
max_covered = 0
for drink, customers in drink_to_customers. items():
covered = sum(1 for customer in customers if customer in unsatisfied)
if covered > max_covered:
max_covered = covered
best_drink = drink
# Remove satisfied customers
if best_drink != - 1 :
for customer in drink_to_customers[best_drink]:
unsatisfied. discard(customer)
drink_count += 1
return drink_count
Complexity#
⏰ Time complexity: O(d * c * n), where d is the number of unique drinks, c is the number of customers, and n is the average number of drinks per customer. In each iteration we check all drinks and their customers
🧺 Space complexity: O(d * c), for storing the drink-to-customers mapping and unsatisfied customer set
Method 2 - Bitmask Dynamic Programming#
Intuition#
For smaller inputs, we can use bitmask DP to find the exact minimum. Each customer can be represented by a bit, and each drink covers a specific subset of customers (represented as a bitmask). We find the minimum number of drinks needed to cover all customer bits.
Approach#
Convert customer preferences to bitmasks where each drink covers certain customer bits
Use DP where dp[mask] represents minimum drinks needed to satisfy customers in the mask
For each state, try adding each possible drink and update the resulting state
Return dp[(1 << num_customers) - 1] which represents all customers satisfied
Code#
Cpp
Go
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
public :
int minDrinks(unordered_map< int , vector< int >>& preferences) {
if (preferences.empty()) return 0 ;
// Map customers to indices
< int > customers;
unordered_map< int , int > customerToIndex;
for (auto & [customer, _] : preferences) {
customerToIndex[customer] = customers.size();
customers.push_back(customer);
}
int n = customers.size();
if (n > 20 ) return greedySolution(preferences); // Fallback for large inputs
// Build drink masks
< int , int > drinkMasks;
for (auto & [customer, drinks] : preferences) {
int customerBit = 1 << customerToIndex[customer];
for (int drink : drinks) {
drinkMasks[drink] |= customerBit;
}
}
// DP: dp[mask] = min drinks to satisfy customers in mask
< int > dp(1 << n, INT_MAX);
dp[0 ] = 0 ;
for (int mask = 0 ; mask < (1 << n); mask++ ) {
if (dp[mask] == INT_MAX) continue ;
for (auto & [drink, drinkMask] : drinkMasks) {
int newMask = mask | drinkMask;
dp[newMask] = min(dp[newMask], dp[mask] + 1 );
}
}
return dp[(1 << n) - 1 ];
}
private :
int greedySolution(unordered_map< int , vector< int >>& preferences) {
// Fallback to greedy for large inputs
< int , vector< int >> drinkToCustomers;
unordered_set< int > allCustomers;
for (auto & [customer, drinks] : preferences) {
allCustomers.insert(customer);
for (int drink : drinks) {
drinkToCustomers[drink].push_back(customer);
}
}
unordered_set< int > unsatisfied = allCustomers;
int drinkCount = 0 ;
while (! unsatisfied.empty()) {
int bestDrink = - 1 ;
int maxCovered = 0 ;
for (auto & [drink, customers] : drinkToCustomers) {
int covered = 0 ;
for (int customer : customers) {
if (unsatisfied.count(customer)) covered++ ;
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
if (bestDrink != - 1 ) {
for (int customer : drinkToCustomers[bestDrink]) {
unsatisfied.erase(customer);
}
drinkCount++ ;
}
}
return drinkCount;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
func minDrinksDP (preferences map [int ][]int ) int {
if len(preferences ) == 0 {
return 0
}
// Map customers to indices
customers := make([]int , 0 )
customerToIndex := make(map [int ]int )
for customer := range preferences {
customerToIndex [customer ] = len(customers )
customers = append(customers , customer )
}
n := len(customers )
if n > 20 {
return minDrinks (preferences ) // Fallback to greedy
}
// Build drink masks
drinkMasks := make(map [int ]int )
for customer , drinks := range preferences {
customerBit := 1 << customerToIndex [customer ]
for _ , drink := range drinks {
drinkMasks [drink ] |= customerBit
}
}
// DP: dp[mask] = min drinks to satisfy customers in mask
dp := make([]int , 1 << n )
for i := range dp {
dp [i ] = math .MaxInt32
}
dp [0 ] = 0
for mask := 0 ; mask < (1 << n ); mask ++ {
if dp [mask ] == math .MaxInt32 {
continue
}
for _ , drinkMask := range drinkMasks {
newMask := mask | drinkMask
if dp [mask ] + 1 < dp [newMask ] {
dp [newMask ] = dp [mask ] + 1
}
}
}
return dp [(1 << n ) - 1 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
public int minDrinks (Map< Integer, List< Integer>> preferences) {
if (preferences.isEmpty ()) return 0;
// Map customers to indices
List< Integer> customers = new ArrayList<> (preferences.keySet ());
Map< Integer, Integer> customerToIndex = new HashMap<> ();
for (int i = 0; i < customers.size (); i++ ) {
customerToIndex.put (customers.get (i), i);
}
int n = customers.size ();
if (n > 20) return greedySolution(preferences); // Fallback for large inputs
// Build drink masks
Map< Integer, Integer> drinkMasks = new HashMap<> ();
for (Map.Entry < Integer, List< Integer>> entry : preferences.entrySet ()) {
int customer = entry.getKey ();
int customerBit = 1 << customerToIndex.get (customer);
for (int drink : entry.getValue ()) {
drinkMasks.put (drink, drinkMasks.getOrDefault (drink, 0) | customerBit);
}
}
// DP: dp[mask] = min drinks to satisfy customers in mask
int [] dp = new int [ 1 << n] ;
Arrays.fill (dp, Integer.MAX_VALUE );
dp[ 0] = 0;
for (int mask = 0; mask < (1 << n); mask++ ) {
if (dp[ mask] == Integer.MAX_VALUE ) continue ;
for (Map.Entry < Integer, Integer> entry : drinkMasks.entrySet ()) {
int drinkMask = entry.getValue ();
int newMask = mask | drinkMask;
dp[ newMask] = Math.min (dp[ newMask] , dp[ mask] + 1);
}
}
return dp[ (1 << n) - 1] ;
}
private int greedySolution (Map< Integer, List< Integer>> preferences) {
// Greedy fallback implementation (same as Method 1)
Map< Integer, List< Integer>> drinkToCustomers = new HashMap<> ();
Set< Integer> allCustomers = new HashSet<> ();
for (Map.Entry < Integer, List< Integer>> entry : preferences.entrySet ()) {
int customer = entry.getKey ();
allCustomers.add (customer);
for (int drink : entry.getValue ()) {
drinkToCustomers.computeIfAbsent (drink, k -> new ArrayList<> ()).add (customer);
}
}
Set< Integer> unsatisfied = new HashSet<> (allCustomers);
int drinkCount = 0;
while (! unsatisfied.isEmpty ()) {
int bestDrink = - 1;
int maxCovered = 0;
for (Map.Entry < Integer, List< Integer>> entry : drinkToCustomers.entrySet ()) {
int drink = entry.getKey ();
List< Integer> customerList = entry.getValue ();
int covered = 0;
for (int customer : customerList) {
if (unsatisfied.contains (customer)) covered++ ;
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
if (bestDrink != - 1) {
for (int customer : drinkToCustomers.get (bestDrink)) {
unsatisfied.remove (customer);
}
drinkCount++ ;
}
}
return drinkCount;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution :
def min_drinks (self, preferences: Dict[int, List[int]]) -> int:
if not preferences:
return 0
# Map customers to indices
customers = list(preferences. keys())
customer_to_index = {customer: i for i, customer in enumerate(customers)}
n = len(customers)
if n > 20 :
return self. _greedy_solution(preferences) # Fallback for large inputs
# Build drink masks
drink_masks = {}
for customer, drinks in preferences. items():
customer_bit = 1 << customer_to_index[customer]
for drink in drinks:
if drink not in drink_masks:
drink_masks[drink] = 0
drink_masks[drink] |= customer_bit
# DP: dp[mask] = min drinks to satisfy customers in mask
dp = [float('inf' )] * (1 << n)
dp[0 ] = 0
for mask in range(1 << n):
if dp[mask] == float('inf' ):
continue
for drink_mask in drink_masks. values():
new_mask = mask | drink_mask
dp[new_mask] = min(dp[new_mask], dp[mask] + 1 )
return dp[(1 << n) - 1 ]
def _greedy_solution (self, preferences: Dict[int, List[int]]) -> int:
# Greedy fallback implementation (same as Method 1)
drink_to_customers = {}
all_customers = set(preferences. keys())
for customer, drinks in preferences. items():
for drink in drinks:
if drink not in drink_to_customers:
drink_to_customers[drink] = []
drink_to_customers[drink]. append(customer)
unsatisfied = set(all_customers)
drink_count = 0
while unsatisfied:
best_drink = - 1
max_covered = 0
for drink, customer_list in drink_to_customers. items():
covered = sum(1 for customer in customer_list if customer in unsatisfied)
if covered > max_covered:
max_covered = covered
best_drink = drink
if best_drink != - 1 :
for customer in drink_to_customers[best_drink]:
unsatisfied. discard(customer)
drink_count += 1
return drink_count
Complexity#
⏰ Time complexity: O(d * 2^n), where d is the number of unique drinks and n is the number of customers. We iterate through all possible customer subsets and try each drink
🧺 Space complexity: O(2^n), for the DP table storing minimum drinks for each customer subset