# Grumpy Bookstore Owner

ArraySliding Window

## # Solution

Both solutions have linear time and space.

### # Unsatisfied Customers (TLE)

Two loops would TLE.

``````def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
n = len(customers)

# unsatisfied customers at instant i
unsatisfied = [0 for _ in range(n)]
for i in range(n):
unsatisfied[i] = 0 if grumpy[i]==0 else customers[i]

# find max continuous sum of unsatisfied customers
secret_sum = 0
for i in range(n+1-X):
secret_sum = max(secret_sum, sum(unsatisfied[i:i+X]))

# return the # of satisfied customers
return sum(customers) - sum(unsatisfied) + secret_sum
``````
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

### # Sliding Window

`base` is the number of customers satisfied if not grumpy. `bonus` is the number of customers gained if owner is not grumpy during `X`.

``````def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
n = len(customers)
base = bonus = window = 0

for i in range(n):
# satisfied already
base += (1-grumpy[i])*customers[i]
# unsatisfied customers if grumpy during X
window += grumpy[i]*customers[i]
# maintain the sliding window
if i >= X:
window -= grumpy[i-X]*customers[i-X]
bonus = max(bonus, window)

# originally satisfied + max bonus if not grumpy during X
return base + bonus
``````
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16