Grumpy Bookstore Owner
MedPrompt
There is a bookstore owner that has a store open for n minutes. You are given an integer array customers of length n where customers[i] is the number of the customers that enter the store at the start of the ith minute and all those customers leave after the end of that minute.
During certain minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.
When the bookstore owner is grumpy, the customers entering during that minute are not satisfied. Otherwise, they are satisfied.
The bookstore owner knows a secret technique to remain not grumpy for minutes consecutive minutes, but this technique can only be used 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], minutes = 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.
Example 2:
Input: customers = [1], grumpy = [0], minutes = 1
Output: 1
Constraints:
n == customers.length == grumpy.length1 <= minutes <= n <= 2 * 1040 <= customers[i] <= 1000grumpy[i]is either0or1.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible continuous window of minutes length. For each window, we calculate the total number of satisfied customers if the owner uses their special technique during that time. We then keep track of the maximum satisfaction score found across all possible windows.
Algorithm
- Initialize
maxTotalSatisfiedto 0. - Iterate through all possible starting positions for the
minutes-long window, fromi = 0ton - minutes. - For each starting position
i, calculate the total number of satisfied customers if the technique is applied to the window[i, i + minutes - 1].- Initialize
currentTotalSatisfiedto 0. - Iterate through all minutes
jfrom0ton-1. - If minute
jis within the technique window (j >= iandj < i + minutes), addcustomers[j]tocurrentTotalSatisfied. - Otherwise, if the owner is not grumpy (
grumpy[j] == 0), addcustomers[j]tocurrentTotalSatisfied.
- Initialize
- Update
maxTotalSatisfied = max(maxTotalSatisfied, currentTotalSatisfied). - After checking all windows, return
maxTotalSatisfied.
Walkthrough
The core idea is to simulate using the technique for every possible start time. A window of minutes can start at any index i from 0 to n - minutes, where n is the total number of minutes.
For each starting index i, we define a window from i to i + minutes - 1. We then calculate the total satisfied customers for this specific choice. A simpler way to structure the calculation is to first find the baseline satisfaction (customers satisfied without the technique). Then, for each window, calculate the additional customers gained and add it to the baseline. The goal is to find the window that provides the maximum additional gain.
We iterate through all possible windows, calculate the gain for each, and find the maximum possible total satisfaction.
class Solution { public int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int n = customers.length; int initiallySatisfied = 0; for (int i = 0; i < n; i++) { if (grumpy[i] == 0) { initiallySatisfied += customers[i]; } } int maxExtraSatisfied = 0; // Iterate through all possible windows for (int i = 0; i <= n - minutes; i++) { int currentExtraSatisfied = 0; // Calculate the gain for the current window for (int j = i; j < i + minutes; j++) { if (grumpy[j] == 1) { currentExtraSatisfied += customers[j]; } } maxExtraSatisfied = Math.max(maxExtraSatisfied, currentExtraSatisfied); } return initiallySatisfied + maxExtraSatisfied; }}Complexity
Time
O(N * M), where N is the length of the `customers` array and M is the `minutes` value. The outer loop runs `N - M + 1` times, and the inner loop runs `M` times. In the worst case, `M` can be close to `N`, leading to O(N^2) complexity.
Space
O(1), as we only use a few variables to store the sums and maximums.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem statement's logic.
Cons
Inefficient due to nested loops, leading to redundant calculations.
The time complexity of O(N * M) can be too slow for large inputs, potentially causing a 'Time Limit Exceeded' error.
This approach improves upon the brute-force method by avoiding redundant calculations. We can think of the problem as finding a window of size minutes that maximizes the number of customers who were initially unsatisfied. A sliding window technique is perfect for this. We calculate the sum for the first window and then slide it one position at a time, updating the sum in constant time by subtracting the element that leaves the window and adding the element that enters.
Algorithm
- First, calculate the base number of satisfied customers. Initialize
initiallySatisfied = 0. Iterate fromi = 0ton-1. Ifgrumpy[i] == 0, addcustomers[i]toinitiallySatisfied. - The goal is now to find the window of size
minutesthat contains the maximum number of customers who were initially unsatisfied. - Initialize a sliding window for the first
minutes. Calculate the extra customers gained in this window (currentExtraSatisfied) by summingcustomers[i]wheregrumpy[i] == 1forifrom0tominutes - 1. - Initialize
maxExtraSatisfied = currentExtraSatisfied. - Slide the window one position at a time from
i = minuteston-1.- In each step, update
currentExtraSatisfiedby adding the new element entering the window (customers[i]) if it was a grumpy minute, and subtracting the element leaving the window (customers[i - minutes]) if it was a grumpy minute. - Update
maxExtraSatisfied = max(maxExtraSatisfied, currentExtraSatisfied).
- In each step, update
- The final result is
initiallySatisfied + maxExtraSatisfied.
Walkthrough
The total number of satisfied customers is the sum of two parts:
- Customers who are satisfied regardless of the technique (when
grumpy[i] == 0). - The maximum number of extra customers we can satisfy by using the technique on a window of
minutes. This is the maximum sum ofcustomers[i]forgrumpy[i] == 1in any window of sizeminutes.
First, we pre-calculate the total number of customers who are satisfied without any special technique. Then, we use a sliding window of size minutes to find the maximum gain possible. We initialize the window to cover the first minutes and calculate the 'extra satisfaction' gained. Then, we slide the window one step to the right, updating the sum by subtracting the leaving element's contribution and adding the entering element's contribution. We repeat this until the window reaches the end, keeping track of the maximum gain seen.
Finally, we add this maximum gain to the initially satisfied customer count.
class Solution { public int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int n = customers.length; int initiallySatisfied = 0; // Calculate the number of customers satisfied without the technique for (int i = 0; i < n; i++) { if (grumpy[i] == 0) { initiallySatisfied += customers[i]; } } // Calculate the extra customers gained in the first window int currentExtraSatisfied = 0; for (int i = 0; i < minutes; i++) { if (grumpy[i] == 1) { currentExtraSatisfied += customers[i]; } } int maxExtraSatisfied = currentExtraSatisfied; // Slide the window from the start to the end of the array for (int i = minutes; i < n; i++) { // Add the new element entering the window if (grumpy[i] == 1) { currentExtraSatisfied += customers[i]; } // Remove the old element leaving the window if (grumpy[i - minutes] == 1) { currentExtraSatisfied -= customers[i - minutes]; } // Update the maximum extra satisfied customers found so far maxExtraSatisfied = Math.max(maxExtraSatisfied, currentExtraSatisfied); } return initiallySatisfied + maxExtraSatisfied; }}Complexity
Time
O(N), where N is the length of the `customers` array. We perform a few separate passes over the array (one for initial satisfaction, one for the first window, and one for sliding), but each pass is linear. The total time is O(N) + O(M) + O(N-M), which simplifies to O(N).
Space
O(1), as we only use a few variables to store the running sums and maximums.
Trade-offs
Pros
Highly efficient with a linear time complexity.
Avoids redundant calculations by reusing the sum from the previous window.
Optimal solution for this problem.
Cons
Slightly more complex to reason about than the straightforward brute-force approach.
Solutions
Solution
class Solution {public int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int s = 0, cs = 0; int n = customers.length; for (int i = 0; i < n; ++i) { s += customers[i] * grumpy[i]; cs += customers[i]; } int t = 0, ans = 0; for (int i = 0; i < n; ++i) { t += customers[i] * grumpy[i]; int j = i - minutes + 1; if (j >= 0) { ans = Math.max(ans, cs - (s - t)); t -= customers[j] * grumpy[j]; } } return ans; }}class Solution {public: int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int minutes) { int s = 0, cs = 0; int n = customers.size(); for (int i = 0; i < n; ++i) { s += customers[i] * grumpy[i]; cs += customers[i]; } int t = 0, ans = 0; for (int i = 0; i < n; ++i) { t += customers[i] * grumpy[i]; int j = i - minutes + 1; if (j >= 0) { ans = max(ans, cs - (s - t)); t -= customers[j] * grumpy[j]; } } return ans; }};class Solution: def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int: s = sum(a * b for a, b in zip(customers, grumpy)) cs = sum(customers) t = ans = 0 for i, (a, b) in enumerate(zip(customers, grumpy), 1): t += a * b if (j: = i - minutes) >= 0: ans = max(ans, cs - (s - t)) t -= customers[j] * grumpy[j] return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.