medium

Grumpy Bookstore Owner

Maximize satisfied customers by calming a grumpy owner for one fixed stretch of minutes.

1. Define the problem

Grumpy Bookstore Owner

Customers arrive each minute; when the owner is grumpy those customers are lost. Once, for minutes consecutive minutes , the owner can stay calm. Maximize satisfied customers: add a baseline of already-happy minutes to the best fixed window of rescued grumpy-minute customers.

Constraints

  • 1 ≤ minutes ≤ customers.length == grumpy.length ≤ 2 × 104
  • 0 ≤ customersi ≤ 1000
  • grumpyi is either 0 or 1

Example

Inputcustomers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output16

Explanation Calm minutes 5–7 to rescue 6 customers; baseline 10 + 6 = 16.

2. Know the words first

In plain terms

Grumpy
In a bad mood — here, a minute where the owner is grumpy means every customer who arrives that minute leaves unhappy and does not count as satisfied.
3. Visualize the solution

Baseline + best rescued grumpy window

Baseline + best rescued grumpy window
Statuswindow

First window rescues 0 grumpy customers (only index 1 is grumpy with 0).

What happens in this step

window = [0, 2]  customers [1, 0, 1]  grumpy [0, 1, 0]

Only index 1 is a grumpy minute, and its customer count is 0, so calming it rescues nothing.

windowRescued = 0 — bestRescued = 0 so far.
Step 1 of 4

Steps to visualize

  1. Sum customers on minutes when the owner is already calm — that is the baseline.
  2. Place a fixed window of length minutes and sum customers only on grumpy minutes.
  3. That window sum is the customers you can rescue by staying calm.
  4. Slide the rescue window and keep the maximum rescued total.
  5. Answer is baseline plus the best rescue window.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Baseline + best rescued grumpy window
Statuswindow

First window rescues 0 grumpy customers (only index 1 is grumpy with 0).

What happens in this step

window = [0, 2]  customers [1, 0, 1]  grumpy [0, 1, 0]

Only index 1 is a grumpy minute, and its customer count is 0, so calming it rescues nothing.

windowRescued = 0 — bestRescued = 0 so far.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function maxSatisfied(customers, grumpy, minutes) {
  const n = customers.length;

  let baseline = 0;
  for (let i = 0; i < n; i++) {
    if (grumpy[i] === 0) baseline += customers[i];
  }

  let windowRescued = 0;
  for (let i = 0; i < minutes; i++) {
    if (grumpy[i] === 1) windowRescued += customers[i];
  }

  let bestRescued = windowRescued;

  for (let right = minutes; right < n; right++) {
    if (grumpy[right] === 1) windowRescued += customers[right];
    const left = right - minutes;
    if (grumpy[left] === 1) windowRescued -= customers[left];
    bestRescued = Math.max(bestRescued, windowRescued);
  }

  return baseline + bestRescued;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 316Docstring example
customers = [5], grumpy = [1], minutes = 15Single minute
customers = [3, 4, 5], grumpy = [0, 0, 0], minutes = 112Owner never grumpy
customers = [3, 4, 5], grumpy = [1, 1, 1], minutes = 29Always grumpy — technique covers max window
customers = [1, 2, 3], grumpy = [1, 0, 1], minutes = 36minutes equals full array length
customers = [4, 4, 4, 4], grumpy = [1, 1, 1, 1], minutes = 28Identical counts, always grumpy
customers = [1,2,3,1,1,7,5,2], grumpy = [0,0,1,1,0,1,0,0], minutes = 319Baseline 11 + best rescue 8

Keep reading

TopicDescription
Sliding WindowSolve fixed-window problems: maximum sum of k elements, moving averages, and O(n) updates as the window slides.
Maximum Average Subarray IFind the contiguous subarray of a fixed length with the largest average.
Longest Substring Without Repeating CharactersFind the length of the longest run of characters in a string with no repeats.
Permutation in StringCheck whether one string contains a rearrangement of another string as a substring.
Minimum Size Subarray SumFind the shortest contiguous subarray whose sum is at least a target value.
Longest Repeating Character ReplacementFind the longest substring you can turn into one repeated letter with a limited number of swaps.