Grumpy Bookstore Owner: Sliding Window Technique

A bookstore owner has a store open for n minutes. During each minute i, customers[i] customers enter the store. The owner is sometimes grumpy: if grumpy[i] == 1, the customers arriving during that minute leave unsatisfied. If grumpy[i] == 0, they leave happy. The owner knows a secret technique to suppress grumpiness for minutes consecutive minutes, making all customers in that window satisfied. You can only use the technique once. Return the maximum number of customers that can be satisfied throughout the day.

This is LeetCode 1052: Grumpy Bookstore Owner, and it is a clean application of the fixed-size sliding window pattern. The trick is decomposing the problem into a fixed part and a variable part, then optimizing only the variable part.

Why this problem matters

Sliding window problems come in two flavors: variable-size windows (where you expand and shrink to find a valid range) and fixed-size windows (where the window length is given). Grumpy Bookstore Owner is a great example of the fixed-size flavor. It teaches you to separate what is already decided from what you can still optimize, then slide a window across only the part you control.

This decomposition skill transfers directly to problems like "Maximum Average Subarray" (LeetCode 643), "Maximum Points You Can Obtain from Cards" (LeetCode 1423), and any problem where you have a fixed budget of changes to apply to a contiguous segment.

The key insight

Some customers are always satisfied, no matter where you place the window. These are the customers who arrive during non-grumpy minutes (grumpy[i] == 0). You can sum those up front and set them aside.

The only thing the secret technique changes is the grumpy minutes that fall inside the window. For those minutes, customers who would have been lost are now rescued. So the question becomes: which window of size minutes rescues the most customers from grumpy minutes?

That is a classic fixed-size sliding window maximum. You slide a window of length minutes across the array, tracking the sum of customers[i] where grumpy[i] == 1 inside the window. The best window gives you the maximum extra satisfaction, and you add that to the base.

The algorithm:

1. Compute the base satisfaction: sum of customers[i] for all i where grumpy[i] == 0.
2. Initialize the window over the first minutes positions. Sum up customers[i] for indices where grumpy[i] == 1 inside this window.
3. Slide the window one position at a time. When a new index enters, add its grumpy customers. When an index leaves, subtract its grumpy customers. Track the maximum.
4. Return base + maximum extra.

The solution

def max_satisfied(customers: list[int], grumpy: list[int], minutes: int) -> int:
    n = len(customers)
    base = 0
    for i in range(n):
        if grumpy[i] == 0:
            base += customers[i]

    extra = 0
    for i in range(minutes):
        if grumpy[i] == 1:
            extra += customers[i]

    best = extra
    for i in range(minutes, n):
        if grumpy[i] == 1:
            extra += customers[i]
        if grumpy[i - minutes] == 1:
            extra -= customers[i - minutes]
        best = max(best, extra)

    return base + best

Let's walk through what each piece does.

The first loop computes the base satisfaction. It sums all customers[i] where the owner is not grumpy. These customers are happy no matter what, so we lock them in and never touch them again.

The second loop initializes the sliding window. It sums customers[i] for the first minutes indices, but only where grumpy[i] == 1. This is the "extra" satisfaction we would gain by placing the technique window at the very start.

The third loop slides the window. At each step, the right edge of the window moves to index i, and the left edge moves past index i - minutes. If the new right edge is a grumpy minute, we add those rescued customers. If the old left edge was a grumpy minute, we subtract those customers (they are no longer rescued). We track the best extra we have seen.

Finally, we return the base plus the best extra. The base is fixed. The extra is the maximum we could rescue with optimal window placement.

Visual walkthrough

Let's trace through the example: customers = [1, 0, 1, 2, 1, 1, 7, 5], grumpy = [0, 1, 0, 1, 0, 1, 0, 1], minutes = 3. Watch how the window slides and tracks rescued customers at each position.

The optimal window lands at indices 5 through 7, rescuing 6 customers who would have been lost. Combined with the base of 10 always-satisfied customers, the answer is 16.

Complexity analysis

Time is O(n). We make three passes over the array: one to compute the base, one to initialize the window, and one to slide it. Each pass is linear, so total work is proportional to the array length.

Space is O(1). We only use a handful of variables (base, extra, best). No additional data structures are needed because the sliding window maintains its state with simple addition and subtraction.

The building blocks

1. Decomposing into fixed and variable parts

The pattern of separating what is already decided from what you can optimize:

base = 0
for i in range(n):
    if grumpy[i] == 0:
        base += customers[i]

This appears whenever a problem has "free" value that you collect regardless of your choices, plus "extra" value that depends on a decision. By computing the fixed part first, you reduce the problem to a simpler optimization over just the variable part. You will see this same decomposition in problems like "Maximum Points You Can Obtain from Cards" and "Minimum Swaps to Group All 1s Together."

2. Fixed-size sliding window maximum

The pattern of sliding a window of known length and tracking the best sum:

extra = sum(customers[i] for i in range(minutes) if grumpy[i] == 1)
best = extra
for i in range(minutes, n):
    if grumpy[i] == 1:
        extra += customers[i]
    if grumpy[i - minutes] == 1:
        extra -= customers[i - minutes]
    best = max(best, extra)

This is the core fixed-size sliding window template. Initialize the window, then slide it one step at a time. Add the new element, remove the old element, update the answer. The same pattern solves "Maximum Average Subarray" (LeetCode 643) and any problem where you need the best contiguous segment of a given length.

3. Conditional accumulation inside a window

Notice that we do not add every element that enters the window. We only add customers[i] when grumpy[i] == 1. This is a filtered sliding window, where the contribution of each element depends on a separate condition array. This variant comes up in problems where elements have "weights" or "flags" that determine whether they count toward the window sum.

Edge cases

Before submitting, think through these scenarios:

• All grumpy minutes: every minute has grumpy[i] == 1. The base is 0, and the answer depends entirely on the best window. The window might not cover the whole array.
• No grumpy minutes: every minute has grumpy[i] == 0. Every customer is already satisfied. The window adds nothing. Return the total sum.
• Window covers the entire array: minutes >= n. You can suppress all grumpiness. Return the total sum of all customers.
• All customers are zero: customers[i] == 0 for every i. The answer is 0 regardless of the window.
• Single minute: n == 1. The window always covers index 0. If grumpy, the technique rescues those customers. If not grumpy, they are already satisfied.

From understanding to recall

You have seen how the fixed-size sliding window pattern works for Grumpy Bookstore Owner: compute the base, slide the window, track the best extra. The logic is clean and the code is short.

But the details that trip people up are real. Do you add to extra before or after checking grumpy? Do you subtract the element at i - minutes or i - minutes + 1? Do you initialize the window with the first minutes elements or the first minutes - 1? These are not conceptual misunderstandings. They are recall gaps, and they show up under interview pressure.

Spaced repetition closes those gaps. You practice writing the base computation, the window initialization, and the slide loop from memory at increasing intervals. After a few rounds, the off-by-one details become automatic. You see "fixed window, maximize sum" in a problem, and the code flows out without hesitation.

Related posts

• The Sliding Window Pattern: A Complete Guide - The foundational guide to both fixed-size and variable-size sliding windows
• Subarray Sum Equals K: Prefix Sums Meet Hash Maps - A different approach to subarray problems using prefix sums and hash maps
• Maximum Average Subarray I: Fixed-Size Sliding Window - The simplest fixed-size sliding window problem, a great warmup before tackling this one

CodeBricks breaks Grumpy Bookstore Owner into its decomposition and sliding window building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sliding window problem shows up in your interview, you do not think about it. You just write it.