Grumpy Bookstore Owner
Medium · Sliding Window · Array · Sliding Window
Problem
A bookstore is open for n minutes. During minute i, customers[i] people come in, and they all leave at the end of that minute. The owner's mood is grumpy[i]: when it is 1 the owner is grumpy and that minute's customers are not satisfied; when it is 0 they are.
The owner knows a trick that keeps them calm for minutes consecutive minutes, and can use it at most once. Return the largest number of customers that can be satisfied over the whole day.
Examples
Input: customers = [4,0,2,6,1], grumpy = [0,1,1,1,0], minutes = 2 Output: 13
Minutes 0 and 4 already satisfy 5 people; keeping calm during minutes 2 and 3 adds 2 + 6.
Input: customers = [5], grumpy = [1], minutes = 1 Output: 5
Using the trick on the only minute satisfies all 5 customers.
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3 Output: 16
The calm minutes satisfy 10. A calm spell over minutes 5 to 7 rescues 1 + 5 more, 16 in all.
Constraints
- n == len(customers) == len(grumpy)
- 1 <= minutes <= n <= 2 · 10^4
- 0 <= customers[i] <= 1000
- grumpy[i] is 0 or 1
Approaches
- Baseline: try every window, recount the day — time O(n²), space O(1)
Follow-up
With two separate calm spells, keep the best single-window gain ending at or before each position (a prefix maximum) and combine it with the window that starts after it: still O(n). With the trick usable on any minutes minutes, not necessarily consecutive, it becomes "take the largest grumpy minutes", a selection problem.
Related problems
Start free on Cariara · Coding problems · System design studio
