---
tags: data_structure_python
---

# Grumpy Bookstore Owner

Today, the bookstore owner has a store open for `customers.length` minutes. Every minute, some number of customers (`customers[i]`) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, `grumpy[i] = 1`, otherwise `grumpy[i] = 0`. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for `X` minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

**Example 1:**

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

**Note:**

- 1 <= X <= customers.length == grumpy.length <= 20000
- 0 <= customers[i] <= 1000
- 0 <= grumpy[i] <= 1

## Solution

### Solution 1: Sliding window (static)

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        beg, m, maxi = 0, len(customers), -float("inf")
        satisfied, unsatisfied = 0, 0
        
        for end in range(m):
            
            if not grumpy[end]: # Find # of satisfied customers.
                satisfied += customers[end]
                customers[end] = 0
            else: # Find # of unsatisfied customers.
                unsatisfied += customers[end]
            
            # Move beg to fix window size X.
            if end-beg+1 > X: 
                unsatisfied -= customers[beg]
                beg += 1
                
            # Find maximum # of unsatisfied customers within window X.
            maxi = max(maxi, unsatisfied)
                
        return maxi + satisfied