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 either 0 or 1.The key idea in Grumpy Bookstore Owner is to maximize the number of satisfied customers by strategically applying a special technique that suppresses the owner's grumpiness for a fixed number of minutes. First, compute the baseline satisfaction by counting customers who are already satisfied when the owner is not grumpy. Then focus on the additional customers that could become satisfied during the special window.
This naturally leads to a sliding window approach. Treat the extra customers gained during grumpy minutes as values in a window of size minutes. As the window moves across the array, keep track of the maximum additional customers that could be converted to satisfied ones. Combine this maximum gain with the baseline satisfaction to obtain the optimal result.
This approach is efficient because each element is processed at most twice. The algorithm runs in O(n) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Baseline Calculation | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Say the store owner uses their power in minute 1 to X and we have some answer A. If they instead use their power from minute 2 to X+1, we only have to use data from minutes 1, 2, X and X+1 to update our answer A.
This approach uses the sliding window technique to maximize the number of satisfied customers by calculating the additional satisfaction obtained by using the non-grumpy technique for a given number of consecutive minutes.
Time Complexity: O(n), as it involves a single pass through the arrays.
Space Complexity: O(1), as no extra space beyond a few variables is used.
1public class MaxSatisfied {
2 public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
3 int totalSatisfaction = 0, maxExtraSatisfaction = 0, currentExtraSatisfaction = 0;
4 int n = customers.length;
5
6 for (int i = 0; i < n; ++i) {
7 if (grumpy[i] == 0) {
8 totalSatisfaction += customers[i];
9 }
10 }
11
12 for (int i = 0; i < n; ++i) {
13 if (grumpy[i] == 1) {
14 currentExtraSatisfaction += customers[i];
15 }
16 if (i >= minutes) {
17 if (grumpy[i - minutes] == 1) {
18 currentExtraSatisfaction -= customers[i - minutes];
19 }
20 }
21 maxExtraSatisfaction = Math.max(maxExtraSatisfaction, currentExtraSatisfaction);
22 }
23
24 return totalSatisfaction + maxExtraSatisfaction;
25 }
26
27 public static void main(String[] args) {
28 int[] customers = {1, 0, 1, 2, 1, 1, 7, 5};
29 int[] grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
30 int minutes = 3;
31 System.out.println("Max satisfied customers: " + maxSatisfied(customers, grumpy, minutes));
32 }
33}This Java solution involves iterating through the customers and grumpy arrays while using a sliding window to determine the largest amount of additional satisfaction achievable by deploying the no-grumpy technique. This approach optimizes performance to achieve a linear runtime complexity.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it is a common medium-level interview problem that tests understanding of arrays and the sliding window pattern. Variations of this technique frequently appear in interviews at major tech companies.
Sliding window works well because the special technique lasts for a fixed number of consecutive minutes. By maintaining a window of that size, we can efficiently track the maximum additional satisfied customers.
Arrays combined with the sliding window technique are sufficient for this problem. No complex data structures are required because the window can be updated in constant time while scanning the array.
The optimal approach uses a sliding window technique. First compute customers already satisfied when the owner is not grumpy, then use a fixed-size window to find the maximum additional customers that could become satisfied.