Grumpy Bookstore Owner — Fixed Sliding Window Bonus (LC 1052)

Problem Statement#

LeetCode 1052 — Grumpy Bookstore Owner (Medium)

A bookstore owner has customers[i] customers at minute i. When grumpy (grumpy[i] = 1), those customers are dissatisfied. The owner can suppress grumpiness for exactly minutes consecutive minutes (once). Return the maximum number of customers that can be satisfied.

Constraints:

• 1 <= minutes <= customers.length <= 2 * 10^4
• 0 <= customers[i] <= 1000
• grumpy[i] is 0 or 1

Input:  customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16

Input:  customers = [4,10,10], grumpy = [1,1,0], minutes = 2
Output: 24

Why This Problem Matters#

This is one of the cleanest formulations of the fixed-window sliding window technique and appears regularly in Google and Amazon phone screens. The real-world framing — a business owner trying to maximize customer satisfaction during a limited intervention window — makes it easy for interviewers to discuss trade-offs and follow-ups.

The problem teaches a key mental model: decompose a mixed objective into a fixed base plus an optimizable bonus. The base (customers in non-grumpy minutes) is fixed regardless of window placement. The bonus (customers in grumpy minutes captured by the suppression window) is what you maximize. This decomposition generalises to caching windows, maintenance windows, and A/B test scheduling — signs of engineering maturity.

The Core Insight#

Split into two parts:

1. Base satisfaction: customers in non-grumpy minutes (grumpy[i] = 0). Always satisfied. Compute once.
2. Bonus satisfaction: customers in grumpy minutes (grumpy[i] = 1) that fall inside the minutes-long suppression window. Maximize by sliding the window.

Total = base + best_bonus. Since base is fixed, slide a window of size minutes and maximize sum(customers[i] * grumpy[i]) inside the window.

Key: only grumpy minutes contribute to the bonus. Non-grumpy minutes inside the window are already in the base — do not double-count them.

Visual Dry Run#

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3

Base (grumpy=0 minutes): 1+1+1+7 = 10

Bonus window (only grumpy=1 contribute):

Total = 10 + 6 = 16

Solution (Optimal)#

def maxSatisfied(customers: list[int], grumpy: list[int], minutes: int) -> int:
    n = len(customers)
 
    base = sum(c for c, g in zip(customers, grumpy) if g == 0)
 
    window_bonus = sum(customers[i] * grumpy[i] for i in range(minutes))
    best_bonus = window_bonus
 
    for i in range(minutes, n):
        window_bonus += customers[i] * grumpy[i]
        window_bonus -= customers[i - minutes] * grumpy[i - minutes]
        best_bonus = max(best_bonus, window_bonus)
 
    return base + best_bonus

var maxSatisfied = function(customers, grumpy, minutes) {
    const n = customers.length;
 
    let base = 0;
    for (let i = 0; i < n; i++) {
        if (grumpy[i] === 0) base += customers[i];
    }
 
    let windowBonus = 0;
    for (let i = 0; i < minutes; i++) {
        windowBonus += customers[i] * grumpy[i];
    }
    let bestBonus = windowBonus;
 
    for (let i = minutes; i < n; i++) {
        windowBonus += customers[i] * grumpy[i];
        windowBonus -= customers[i - minutes] * grumpy[i - minutes];
        bestBonus = Math.max(bestBonus, windowBonus);
    }
 
    return base + bestBonus;
};

Time: O(n) — two passes: one for base, one for sliding window Space: O(1) — no auxiliary data structures

Common Mistakes#

• Adding all customers in the window (not just grumpy ones) — double-counts non-grumpy customers already in the base
• Not computing the base separately — recomputing total from scratch for each window is O(n * minutes)
• Greedy placement at the single highest-customer minute — ignores cumulative bonus; must try all window positions
• Off-by-one in the initial window — initialise with range(0, minutes), not range(1, minutes)
• Using a variable-size window — the suppression duration is exactly minutes; use a fixed window

Interview Tips#

• Lead with the decomposition: "The base is fixed. I only need to maximize the bonus from grumpy minutes in the suppression window"
• customers[i] * grumpy[i] elegantly computes per-minute bonus: grumpy=0 contributes 0, grumpy=1 contributes the full count
• The outgoing element is customers[i - minutes] * grumpy[i - minutes] — mixing up which index to remove is the most common implementation bug
• The interviewer may ask: "What if the technique can be used multiple times?" — that becomes a DP problem

Follow-up Questions#

• Multiple non-overlapping windows: if the technique can be used t times without overlap, it becomes a DP problem
• Continuous grumpy probabilities: same sliding window; bonus becomes customers[i] * grumpy_probability[i]
• Variable window size: maximise over both position and size — requires prefix sums

Key Takeaways#

• Decompose into fixed base (non-grumpy minutes) plus variable bonus (grumpy minutes in the suppression window)
• Slide a fixed window of exactly minutes length; only grumpy minutes (grumpy[i] = 1) contribute to bonus
• customers[i] * grumpy[i] computes per-minute bonus without a conditional branch
• Outgoing element when right edge is at i is customers[i - minutes] * grumpy[i - minutes]
• Time O(n), space O(1) — two passes total; decompose-then-slide pattern generalises widely