⚡Flashcard Drill➔
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

  1. Customers are always satisfied when the owner is not grumpy; call that the baseline.
  2. The technique can additionally recover the customers in one window of length minutes where the owner is grumpy.
  3. So slide a window of that length, summing only the grumpy-minute customers, and take the maximum extra gain.
  4. 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 of grumpy[i-minutes]: only grumpy minutes were added, so only they should be removed.
  • Using a while loop to shrink the window: the window has a fixed length, so a simple if eviction is correct.
  • Forgetting the baseline: the technique only affects minutes minutes; 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems