Grumpy Bookstore Owner
Companies: Nutanix, Google
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 ith 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 :
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:
Using a sliding window approach will help us to solve this problem efficiently. Use a sliding window winOfMakeSatisfied
to record the number of unsatisfied customers for X minutes. Deduct the unsatisfied customers from left end of the sliding window when it is wider than X, i.e. winOfMakeSatisfied = grumpy[i  X] * customers[i  X]
. Now, use satisfied to record the number of satistified customers without grumpy technique. After this iteration, our answer will be satisfied + max(winOfMakeSatisfied)
.
Implementation:
Java:
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X){
int satisfied = 0, maxMakeSatisfied = 0;
for (int i = 0, winOfMakeSatisfied = 0; i < grumpy.length; ++i) {
if (grumpy[i] == 0) { satisfied += customers[i]; }
else { winOfMakeSatisfied += customers[i]; }
if (i >= X) {
winOfMakeSatisfied = grumpy[i  X] * customers[i  X];
}
maxMakeSatisfied = Math.max(winOfMakeSatisfied, maxMakeSatisfied);
}
return satisfied + maxMakeSatisfied;
}
}
Complexity Analysis:

Time Complexity: O(n)

Space Complexity: O(1)