LeetCode 1052: Grumpy Bookstore Owner

Problem Restatement

A bookstore owner has customers arriving each minute, recorded in customers.

The owner is grumpy on some minutes, recorded in grumpy (1 = grumpy, 0 = not grumpy).

When the owner is grumpy, customers that minute are not satisfied.

The owner can suppress grumpiness for minutes consecutive minutes.

Return the maximum number of satisfied customers.

The official constraints state that customers.length == grumpy.length == n, 1 <= minutes <= n <= 2 * 10^4, and 0 <= customers[i] <= 1000.

Input and Output

Function shape:

def maxSatisfied(customers: list[int], grumpy: list[int], minutes: int) -> int:
    ...

Examples

Example 1:

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

Base satisfied (owner not grumpy): minutes 0, 2, 4, 6 → 1+1+1+7 = 10.

Extra if we use the window on minutes 4-6: 0 (already happy at 4 and 6). On minutes 3-5: 2 + 1 = 3.

But the last minute (7) gives 5 extra if we suppress grumpiness at 5-7.

Best window [5,6,7]: extra = 1 + 0 + 5 = 6. Total = 10 + 6 - 0 = 16? Wait let me recompute.

Suppress minutes 5-7 (indices 5,6,7):

• Base: indices where grumpy=0: 0,2,4,6 → 1+1+1+7=10.
• Extra from window: grumpy[5]=1 → customers[5]=1; grumpy[6]=0 (already counted); grumpy[7]=1 → customers[7]=5. Extra = 1+5=6.
• Total = 10 + 6 = 16.

Answer:

16

Key Insight

Base satisfied customers = sum of customers[i] where grumpy[i] == 0.

Extra from the minutes-window = sum of customers[i] where grumpy[i] == 1 in the window.

Use a sliding window of size minutes to find the window that maximizes the extra.

Edge Cases

• Handle windows that never become valid.
• Update counts when both expanding and shrinking the window so stale characters do not remain in the state.
• For fixed-size windows, record the answer only after the window has exactly the required length.

Common Pitfalls

• Do not count a window before it satisfies the required size or validity condition.
• When removing the left character, delete zero-count entries if the algorithm uses the number of keys.

Implementation

class Solution:
    def maxSatisfied(self, 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)
        extra = sum(customers[i] * grumpy[i] for i in range(minutes))
        best_extra = extra

        for i in range(minutes, n):
            extra += customers[i] * grumpy[i]
            extra -= customers[i - minutes] * grumpy[i - minutes]
            best_extra = max(best_extra, extra)

        return base + best_extra

Testing

def run_tests():
    s = Solution()

    assert s.maxSatisfied([1,0,1,2,1,1,7,5], [0,1,0,1,0,1,0,1], 3) == 16
    assert s.maxSatisfied([1], [0], 1) == 1
    assert s.maxSatisfied([1], [1], 1) == 1

    print("all tests passed")

run_tests()