Grumpy Bookstore Owner
Problem
Given arrays customers and grumpy of equal length and an integer minutes, return the maximum number of customers that can be satisfied by using a secret technique to keep the owner not grumpy for a continuous window of length minutes.
- 1 ≤ customers.length == grumpy.length ≤ 20000
- 0 ≤ customers[i] ≤ 1000
- grumpy[i] is 0 or 1
- 1 ≤ minutes ≤ customers.length
Example
customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 316Initially, customers satisfied without the technique are those at indices where grumpy[i] == 0: indices 0, 2, 4, 6, totaling 1 + 1 + 1 + 7 = 10. The technique can be applied to a window of length 3 to convert grumpy minutes to non-grumpy. Applying it from index 5 to 7 covers grumpy minutes at indices 5 and 7, adding customers[5] + customers[7] = 1 + 5 = 6 more satisfied customers. The total maximum satisfied customers is 10 + 6 = 16.
Approach
Straightforward Solution
A brute-force approach would consider every possible window of length minutes, summing the customers during grumpy minutes in that window and adding the customers during non-grumpy minutes outside the window. This approach is O(n * minutes), which is inefficient for large inputs.
Core Observation
The total satisfied customers equals the sum of customers during non-grumpy minutes plus the maximum additional customers that can be gained by applying the technique to a continuous window of length minutes covering grumpy minutes.
Path to Optimal
The key insight is to separate the problem into two parts: (1) sum of customers during non-grumpy minutes (fixed), and (2) maximum sum of customers during grumpy minutes in any window of length minutes. The second part can be efficiently computed using a sliding window that tracks the sum of customers during grumpy minutes within the current window. By sliding this window across the array, the maximum extra customers gained by the technique can be found in O(n) time.
Optimal Approach
Iterate through the arrays once, accumulating the base satisfied customers from non-grumpy minutes. Simultaneously, maintain a sliding window of size minutes over the grumpy minutes to track the extra customers that can be gained by applying the technique. Update the maximum extra customers found. Finally, return the sum of base satisfied customers and the maximum extra customers.
Time
O(n)
The solution iterates through the customers array once, updating sums and sliding the window in constant time per iteration, resulting in linear time complexity.
Space
O(1)
Only a fixed number of integer variables are used to track sums and indices, so the auxiliary space is constant regardless of input size.
Pattern Spotlight
Sliding Window (Fixed-Size Window Sum Optimization)
When needing to find the maximum sum of a subarray of fixed length under certain conditions, use a sliding window to add the new element and remove the oldest element efficiently, avoiding recomputation and achieving O(n) time.
Solution
| 1 | class Solution: |
| 2 | def maxSatisfied(self, customers: list[int], grumpy: list[int], minutes: int) -> int: |
| 3 | base = 0 |
| 4 | extra = 0 |
| 5 | best_extra = 0 |
| 6 | |
| 7 | for i in range(len(customers)): |
| 8 | if grumpy[i] == 0: |
| 9 | base += customers[i] |
| 10 | else: |
| 11 | extra += customers[i] |
| 12 | |
| 13 | if i >= minutes and grumpy[i - minutes] == 1: |
| 14 | extra -= customers[i - minutes] |
| 15 | |
| 16 | if i >= minutes - 1: |
| 17 | best_extra = max(best_extra, extra) |
| 18 | |
| 19 | return base + best_extra |
Step-by-Step Solution
Accumulate Base Satisfaction and Track Extra Customers with Sliding Window
| 3 | base = 0 |
| 4 | extra = 0 |
| 5 | best_extra = 0 |
| 7 | for i in range(len(customers)): |
| 8 | if grumpy[i] == 0: |
| 9 | base += customers[i] |
| 10 | else: |
| 11 | extra += customers[i] |
| 13 | if i >= minutes and grumpy[i - minutes] == 1: |
| 14 | extra -= customers[i - minutes] |
| 16 | if i >= minutes - 1: |
| 17 | best_extra = max(best_extra, extra) |
Objective
To compute the total customers satisfied without the technique and simultaneously track the extra customers gained by applying the technique over a sliding window of length minutes.
Key Insight
Separating customers into those satisfied regardless of grumpiness and those only satisfied if the technique is applied allows efficient calculation. The sliding window accumulates extra customers from grumpy minutes within the current window by adding the new element and removing the element that falls out of the window, maintaining the sum in O(1) time per iteration. This approach avoids recomputing sums for every window, reducing complexity from O(n*minutes) to O(n).
Interview Quick-Check
Core Logic
The algorithm maintains two sums: 'base' for customers satisfied without the technique and 'extra' for customers satisfied by applying the technique in the current window, updating 'extra' efficiently using a sliding window.
State & Boundaries
The sliding window starts accumulating extra customers only after the first 'minutes' elements, ensuring the window size is fixed.
Common Pitfalls & Bugs
Forgetting to subtract the customer count leaving the window when sliding causes incorrect extra sums and wrong results.
Complexity
This single-pass approach achieves O(n) time and O(1) space, optimal for the problem constraints.
Return Maximum Total Satisfied Customers
| 19 | return base + best_extra |
Objective
To combine the base satisfied customers and the best extra customers from the sliding window to produce the final maximum satisfaction count.
Key Insight
The final answer is the sum of customers satisfied without the technique plus the maximum extra customers gained by applying the technique optimally. Returning this sum completes the problem by integrating both fixed and variable satisfaction components.
Interview Quick-Check
Core Logic
Returning base + best_extra correctly accounts for all customers satisfied, both inherently and through the technique.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
extra -= customers[i - minutes]Subtract customers leaving the sliding window if that minute was grumpy.
This line's placement is critical to maintain the sliding window's fixed size and correct sum by removing the contribution of the minute that falls out, ensuring the extra customers count reflects only the current window.
best_extra = max(best_extra, extra)Update the best extra customers if the current window sum is greater.
This max operation is the core of the sliding window optimization, capturing the best possible extra gain by comparing the current window's extra customers to the best found so far.
extra = 0Initialize extra customers count within the current sliding window to zero.
This variable tracks customers that can be additionally satisfied by applying the technique in the current window, enabling efficient updates as the window slides.
best_extra = 0Initialize the best extra customers found so far to zero.
This variable stores the maximum extra customers achievable by applying the technique in any window, ensuring the final answer is optimal.
extra += customers[i]Add customers at grumpy minute to the current extra window sum.
This accumulates potential extra satisfied customers that can be gained by applying the technique in the current window.
return base + best_extraReturn the sum of base satisfied customers and the best extra customers.
Combining fixed and variable satisfaction counts yields the maximum total customers satisfied after optimally applying the technique.
base = 0Initialize base satisfied customers count to zero.
This variable accumulates customers satisfied during non-grumpy minutes, forming the fixed part of the total satisfaction.
if grumpy[i] == 0:Check if the owner is not grumpy at the current minute.
Non-grumpy minutes contribute directly to base satisfaction, which is fixed and independent of the technique.
base += customers[i]Add customers at non-grumpy minute to base satisfaction.
This ensures all inherently satisfied customers are counted separately from those potentially gained by the technique.
else:Handle the case where the owner is grumpy at the current minute.
Customers at grumpy minutes are only satisfied if the technique is applied, so they contribute to the extra count within the sliding window.
if i >= minutes and grumpy[i - minutes] == 1:Check if the sliding window has exceeded the allowed size.
Once the window size surpasses minutes, the oldest element must be removed to maintain a fixed window size.
if i >= minutes - 1:Check if the sliding window has reached the required size to consider updating best extra.
Only after the window is fully formed can the algorithm evaluate if the current extra sum is the best found so far.
for i in range(len(customers)):Iterate over each minute index in the customers array.
This loop processes each minute to update base and extra satisfaction counts and slide the window, enabling a single-pass solution.
Test Your Understanding
Why is it sufficient to consider only a single sliding window of length minutes to maximize the extra satisfied customers?
Because the technique can only be applied to one continuous window of length minutes, and the extra satisfied customers come exclusively from grumpy minutes within that window. Sliding the window across all possible positions ensures all candidate windows are evaluated, guaranteeing the maximum extra gain is found.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Grumpy Bookstore Owner from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Grumpy Bookstore Owner drill