Problem Statement

Grumpy Bookstore Owner

A bookstore is open for n minutes. Each minute, some customers walk in. The number who walk in at minute i is customers[i]. The owner has a mood swing: at some minutes he is grumpy (grumpy[i] = 1) and at others he is calm (grumpy[i] = 0). When he is grumpy, every customer who walked in that minute leaves unhappy. When he is calm, they leave happy. The owner has one trick he can use: he can stay calm for a stretch of "minutes" minutes in a row, but only one stretch, and the stretch must be that exact length. We want the largest number of happy customers he can end up with. Here is the plan. First, count every customer who arrives during a calm minute. They are happy no matter what, so call that the baseline. Then we look for the best stretch of grumpy minutes to cancel out, because using the trick there turns those unhappy customers into happy ones. To find the best stretch, we slide a window of length "minutes" across the array and add up the grumpy customers inside it.

mediumSliding WindowSliding WindowTime: 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).

Trace it on `customers=[1,0,1,2,1,1,7,5], grumpy=[0,1,0,1,0,1,0,1], minutes=3`

baseline = customers at grumpy==0 (idx 0,2,4,6) = 1+1+1+7 = 10
initial window [0..2], grumpy minute idx1=0 -> window_gain=0, max_gain=0
right=3: grumpy[3]=1 add +2 -> window_gain=2; grumpy[0]=0 no sub; max_gain=2
right=4: grumpy[4]=0 no add; grumpy[1]=1 sub -0 -> window_gain=2; max_gain=2
right=5: grumpy[5]=1 add +1 -> window_gain=3; grumpy[2]=0 no sub; max_gain=3
right=6: grumpy[6]=0 no add; grumpy[3]=1 sub -2 -> window_gain=1; max_gain=3
right=7: grumpy[7]=1 add +5 -> window_gain=6; grumpy[4]=0 no sub; max_gain=6
return baseline + max_gain = 10 + 6 = 16

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.

Shape of the loop

baseline = sum(customers[i] where grumpy[i] == 0)
window_gain = sum(customers[i] for i in 0..minutes where grumpy[i] == 1)
max_gain = window_gain
for right in minutes..n:
    if grumpy[right]: window_gain += customers[right]
    if grumpy[right-minutes]: window_gain -= customers[right-minutes]
    max_gain = max(max_gain, window_gain)
return baseline + max_gain

Pseudocode only — the full worked solution lives in the Solution tab.

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.

Sliding Window Pattern