Grumpy Bookstore Owner
mediumTime: O(n)Space: O(1)
Recognize the pattern
maximize satisfied customerssome minutes the owner is grumpyuse secret technique for k consecutive minutes
Brute force idea
Try every window of size k — O(n × k). Each window independently summed.
Better approach
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).
Key invariant
Always-satisfied customers are counted once upfront. The sliding window only tracks the ADDITIONAL customers saved by the k-minute technique.
Watch out for
Counting all customers in the window — only count customers during grumpy minutes (grumpy[i] == 1). Non-grumpy customers are already satisfied.