Watch 10 video solutions for Grumpy Bookstore Owner, a medium level problem involving Array, Sliding Window. This walkthrough by NeetCodeIO has 13,605 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |