Lifetime Pro for $29 · One-time payment
Ends inView offer

Grumpy Bookstore Owner

Medium22 min
During minute i, customers[i] customers enter. They are satisfied when grumpy[i] == 0 and unsatisfied when grumpy[i] == 1. The owner may suppress grumpiness for exactly minutes consecutive minutes. Return the maximum number of satisfied customers.

Some customers are satisfied regardless of which window the owner chooses. Whenever grumpy[i] == 0, add customers[i] to the baseline. Choosing the window cannot make those customers any more satisfied because they are already counted.

The chosen window can help only during minutes when grumpy[i] == 1. If the window covers minute i, the customers[i] customers from that minute become satisfied. A calm minute contributes nothing extra because its customers are already included in the baseline.

The remaining task is to find the length-minutes window containing the largest number of otherwise unsatisfied customers. Maintain that extra gain with a fixed-size sliding window.

The final answer is the customers who were already satisfied plus the largest extra gain from one chosen window: baseline + best_gain.

Which customers belong in the baseline?

1 / 3
baseline
0
possible extra
not built
Step 1 of 3.
A grumpy value of 0 means those customers are already satisfied. A value of 1 means they are not.
  • already satisfied
  • newly satisfied if chosen

For each length-minutes window, add customers[i] only when grumpy[i] == 1. Those are the customers who would become satisfied if the owner suppressed grumpiness during that block. Keep the largest block sum.

Which two-minute block creates the largest extra gain?

1 / 5
left
0
right
0
customers in window
4
newly satisfied
0
best gain
not ready
Step 1 of 5.
Start with minute 0. The window contains 4 customers, but they are already satisfied, so the new gain is 0.
  • newly satisfied in current window
  • already satisfied in current window

The baseline counts customers from minutes where grumpy[i] == 0. The window gain counts customers only from covered minutes where grumpy[i] == 1. Since each minute belongs to only one of those groups, adding the two totals does not count any customer twice.

Why does the window count customers only during grumpy minutes?
1def max_satisfied(customers: list[int], grumpy: list[int], minutes: int) -> int:
2 baseline = 0
3
4 for i in range(len(customers)):
5 if grumpy[i] == 0:
6 baseline += customers[i]
7
8 window_gain = 0
9
10 for i in range(minutes):
11 if grumpy[i] == 1:
12 window_gain += customers[i]
13
14 best_gain = window_gain
15
16 for right in range(minutes, len(customers)):
17 if grumpy[right] == 1:
18 window_gain += customers[right]
19
20 left = right - minutes
21 if grumpy[left] == 1:
22 window_gain -= customers[left]
23
24 best_gain = max(best_gain, window_gain)
25
26 return baseline + best_gain
Time: O(n)Space: O(1)

The baseline pass, first-window setup, and remaining window scan process each minute a constant number of times, giving O(n) time. The algorithm stores only the baseline, current window gain, and best gain, so auxiliary space is O(1).