# 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

| Item | Meaning |
|---|---|
| Input | `customers`, `grumpy`, `minutes` |
| Output | Maximum customers satisfied |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| Standard example | `16` | Best window adds 6 extra |
| Single happy minute | `1` | Already satisfied |
| Single grumpy minute | `1` | Suppress grumpiness |