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.Problem Overview: You run a bookstore where the owner is sometimes grumpy. When grumpy, customers during that minute leave unsatisfied. A secret technique can suppress grumpiness for X consecutive minutes. The goal is to choose the best window of X minutes that maximizes the total number of satisfied customers.
Approach 1: Brute Force Window Check (O(n * X) time, O(1) space)
Start by counting customers that are already satisfied when the owner is not grumpy. Then try every possible window of length X. For each window, iterate through its elements and add the customers that would become satisfied if grumpiness were suppressed there. Track the maximum extra satisfaction across all windows. This approach is straightforward but inefficient because each candidate window requires scanning up to X elements, producing O(n * X) time complexity.
Approach 2: Sliding Window for Extra Satisfaction (O(n) time, O(1) space)
The key insight: only customers during grumpy minutes matter for the special technique. First compute the baseline satisfaction by iterating once and summing customers where grumpy[i] == 0. Next, treat the extra customers gained from suppressing grumpiness as a sliding window problem. While scanning the array, add customers[i] to the window if grumpy[i] == 1. When the window size exceeds X, remove the contribution at i - X. Track the maximum extra gain seen in any window.
This converts repeated window recomputation into incremental updates. Each element enters and leaves the window once, so the total work is linear. The algorithm relies on sequential iteration and constant updates, a common pattern in sliding window problems. Since the data is stored in simple arrays, the logic also fits naturally within typical array traversal patterns.
After scanning the entire array, add the maximum extra satisfaction from the window to the baseline satisfied customers. The result represents the optimal placement of the grumpiness suppression technique.
Recommended for interviews: Interviewers expect the sliding window solution. The brute force method shows you understand the objective—testing every possible window—but the O(n) sliding window demonstrates stronger algorithmic thinking and the ability to optimize repeated computations. This pattern appears frequently in array optimization problems where a fixed-length segment must be chosen to maximize or minimize a value.
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.
This solution calculates the initial base satisfaction for all non-grumpy minutes. It then uses a sliding window to determine the maximum additional satisfaction from applying the no-grumpy technique over any possible time frame. The approach efficiently ensures a time complexity of O(n), only making a single linear traversal of the input.
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.
According to the problem description, we only need to count the number of customers when the boss is not angry tot, and add the maximum number of customers when the boss is angry within a sliding window of size minutes mx.
We define a variable cnt to record the number of customers when the boss is angry within the sliding window, the initial value is the number of customers when the boss is angry in the first minutes. Then we traverse the array, each time we move the sliding window, we update the value of cnt, and at the same time update the value of mx.
Finally, return tot + mx.
The time complexity is O(n), where n is the length of the array customers. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sliding Window for Extra Satisfaction | 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. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Window Check | O(n * X) | O(1) | When first reasoning about the problem or when constraints are very small |
| Sliding Window for Extra Satisfaction | O(n) | O(1) | Optimal solution for large arrays; interview-preferred approach |
Grumpy Bookstore Owner - Leetcode 1052 - Python • NeetCodeIO • 13,605 views views
Watch 9 more video solutions →Practice Grumpy Bookstore Owner with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor