Grumpy Bookstore Owner
franklinqin0 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
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16