Grumpy Bookstore Owner
mediumTime: O(n)Space: O(1)
Signals to notice
maximize satisfied customerssome minutes the owner is grumpyuse secret technique for k consecutive minutes
Brute force first
Try every window of size k — O(n × k). Each window independently summed.
The key insight
Base satisfaction = sum of customers[i] where grumpy[i] == 0. Sliding window of size k: compute additional satisfaction gained by suppressing grumpiness. Maximize the additional gain. O(n).
What must stay true
Always-satisfied customers are counted once upfront. The sliding window only tracks the ADDITIONAL customers saved by the k-minute technique.
Easy way to go wrong
Counting all customers in the window — only count customers during grumpy minutes (grumpy[i] == 1). Non-grumpy customers are already satisfied.