NeetCode #224LC-1052MediumSliding Window
← Back to All Problems#224 · #1052 · Grumpy Bookstore Owner(爱生气的书店老板)
📌 Problem Statement & Constraints
A bookstore owner has
customers[i] customers at minute i and a grumpy[i] flag that is 1 when they are grumpy (in which case those customers do not buy). The owner can use a secret technique for minutes consecutive minutes to make themselves not grumpy. Return the maximum number of satisfied customers. Constraints: 1 <= customers.length == grumpy.length <= 2 * 10^4, 0 <= customers[i] <= 1000.💡 Core Algorithmic Approaches
- Customers are always satisfied when the owner is not grumpy; call that the baseline.
- The technique can additionally recover the customers in one window of length
minuteswhere the owner is grumpy. - So slide a window of that length, summing only the grumpy-minute customers, and take the maximum extra gain.
- The answer is the baseline plus that maximum gain.
💻 Benchmark Python3 Implementation
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
n = len(customers)
# baseline: customers served when the owner is not grumpy
base = sum(c for c, g in zip(customers, grumpy) if g == 0)
# extra: the best window of `minutes` of grumpy customers
cur = 0
best = 0
for i in range(n):
if grumpy[i] == 1:
cur += customers[i]
if i >= minutes and grumpy[i - minutes] == 1:
cur -= customers[i - minutes] # left the window
best = max(best, cur)
return base + best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass for the baseline and one sliding pass.
💾 Space Complexity
O(1): two accumulators.
⚠️ Interview Pitfalls & Follow-ups
- Including non-grumpy customers in the window sum: they are already counted in the baseline, so only grumpy minutes should contribute to the extra gain.
- Evicting based on
customers[i-minutes]instead ofgrumpy[i-minutes]: only grumpy minutes were added, so only they should be removed. - Using a
whileloop to shrink the window: the window has a fixed length, so a simpleifeviction is correct. - Forgetting the baseline: the technique only affects
minutesminutes; all other non-grumpy minutes still contribute.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#225 · #487Max Consecutive Ones II