Grumpy Bookstore Owner

How it works

Instead of recalculating the saved customers for each window position from scratch, we can use a sliding window to efficiently update the count. As the window moves one position to the right, we add the contribution of the new element entering the window and remove the contribution of the element leaving.

This reduces redundant computation since we only need to track customers at grumpy minutes within the current window.

Steps

1. Initialize two counters: satisfied for customers already happy (non-grumpy minutes) and window for customers saved within the current window.
2. Use two pointers l and r to represent the sliding window boundaries.
3. For each position r:
   • If grumpy at r, add those customers to the window count.
   • Otherwise, add them to the baseline satisfied count.
   • If the window exceeds minutes, shrink from the left by removing contributions at l (only if grumpy).
   • Track the maximum window value seen.
4. Return satisfied + maxWindow.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Counting Already-Satisfied Customers in the Window

A common mistake is including customers who are already satisfied (when grumpy[i] = 0) in the window's "saved" count. The technique only helps during grumpy minutes, so only customers at indices where grumpy[i] = 1 should be added to the window sum. Counting non-grumpy customers in the window leads to double-counting since they are already part of the baseline satisfaction.

Off-by-One Errors in Window Boundaries

When implementing the sliding window, it is easy to miscalculate when to shrink the window. The window should have exactly minutes elements, so the condition should check if r - l + 1 > minutes before removing the left element. Using >= instead of > or forgetting to increment the left pointer after removal causes incorrect window sizes.

Forgetting to Track the Maximum Window Value

Some solutions correctly compute the window sum but forget to track the maximum value seen across all window positions. The final answer requires the best possible window, not just the last one computed. Always update maxWindow after each window adjustment to capture the optimal placement of the technique.

from typing import List

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        l = 0
        window = max_window = 0
        satisfied = 0

        for r in range(len(customers)):
            if grumpy[r]:
                window += customers[r]
            else:
                satisfied += customers[r]

            if r - l + 1 > minutes:
                if grumpy[l]:
                    window -= customers[l]
                l += 1

            max_window = max(window, max_window)

        return satisfied + max_window

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int l = 0, window = 0, maxWindow = 0, satisfied = 0;

        for (int r = 0; r < customers.size(); r++) {
            if (grumpy[r] == 1) {
                window += customers[r];
            } else {
                satisfied += customers[r];
            }

            if (r - l + 1 > minutes) {
                if (grumpy[l] == 1) {
                    window -= customers[l];
                }
                l++;
            }

            maxWindow = max(window, maxWindow);
        }

        return satisfied + maxWindow;
    }
};