Maximum Satisfied Customers (the "Grumpy Bookstore Owner") is a classic fixed-size sliding window problem dressed up in a story. The trick is to split the answer into a part you cannot change and a part you can optimize over a window.
Problem. A bookstore owner has customers[i] customers arriving in minute i. On minute i the
owner is grumpy if grumpy[i] == 1, and grumpy minutes make every customer that minute unsatisfied.
The owner can use a secret technique to stay calm for X consecutive minutes, once. Return the
maximum number of satisfied customers.
Example: customers = [1, 0, 1, 2, 1, 1, 7, 5], grumpy = [0, 1, 0, 1, 0, 1, 0, 1], X = 3 →
answer 16.
The slow way first
The obvious idea: try placing the calm window at every starting minute, and for each placement re-count all satisfied customers from scratch. That is O(n · X) (or O(n²) if X is large) — we keep re-summing the same minutes over and over.
The question to ask: which customers are even affected by my choice? The customers on non-grumpy minutes are always satisfied no matter what I do. Only the grumpy minutes are up for grabs — and only the ones I cover with my calm window.
The idea: a fixed base plus a sliding bonus
Split the answer into two pieces:
- base — customers on every non-grumpy minute. These are guaranteed, so add them up once.
- extra — among the grumpy minutes, the ones I cover with my
X-minute calm window get recovered. I want the window placement that recovers the most.
So the answer is base + max recoverable extra. Finding the best window is a fixed-size sliding window: slide a width-X window across the array, keep a running sum of grumpy-minute customers inside it, and track the best sum seen.
The key insight: when the window slides one minute, only two minutes change — one leaves the left, one enters the right. So each slide is O(1) instead of re-summing the whole window.
Walk through it
Step through the animation. The bottom row is the grumpy flag; the top row is the customer count, with non-grumpy minutes already green (part of base = 10). The window of width 3 slides right one minute at a time. We add the entering minute's customers if it is grumpy and subtract the leaving minute's if it was grumpy. The best window [5, 7] recovers 1 + 5 = 6, so the answer is 10 + 6 = 16.
Pseudocode
base = sum of customers on minutes where grumpy == 0
extra = sum of customers on grumpy minutes in the first X minutes
best = extra
for hi from X to n-1:
lo = hi - X # minute leaving the window
if grumpy[hi]: extra += customers[hi] # entering minute
if grumpy[lo]: extra -= customers[lo] # leaving minute
best = max(best, extra)
return base + bestThe Python solution
def max_satisfied(customers, grumpy, X):
base = sum(c for c, g in zip(customers, grumpy) if g == 0)
extra = sum(customers[i] for i in range(X) if grumpy[i])
best = extra
for hi in range(X, len(customers)):
lo = hi - X
if grumpy[hi]:
extra += customers[hi]
if grumpy[lo]:
extra -= customers[lo]
best = max(best, extra)
return base + bestbasecounts every customer on a non-grumpy minute — these are always satisfied.extrais seeded with the grumpy-minute customers in the first window[0, X-1].besttracks the largestextrawe have seen across all window placements.- In the loop,
hiis the minute entering the window andlo = hi - Xis the minute leaving it. - We add
customers[hi]only when that minute is grumpy, and subtractcustomers[lo]only when the leaving minute was grumpy — keepingextracorrect in O(1) per slide. - The answer is the fixed
baseplus the best recoverableextra.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (re-sum each placement) | O(n · X) (moderate) | recount window every time |
| Sliding window (this solution) | O(n) (moderate) | O(1) per slide |
O(1) (fast)We do one pass to build base, then one pass to slide the window, each O(1) per step. No extra arrays are needed, so space is O(1).
When this pattern shows up
Whenever a problem fixes a window of size k and asks for the best sum/count over all windows, reach
for a fixed-size sliding window: compute the first window, then add the entering element and remove
the leaving one on each slide. "Max sum subarray of size k" and "max average subarray" are the same move.
Do not fold the always-satisfied customers into the window. The base is fixed; the window should only account for the grumpy minutes you recover. Mixing them double-counts non-grumpy customers.
Practice
With the window at [5, 7], grumpy minutes inside are 5 and 7 with customers 1 and 5. What is extra, and does it beat the previous best of 3?
1. Why split the answer into base + extra?
2. When the window slides by one minute, how many elements change?
3. What is the time complexity of the sliding-window solution?
4. What extra space does this solution use?