Grumpy Bookstore Owner

medium sliding window array prefix sum

Problem

A bookstore is open for n minutes. customers[i] customers arrive at minute i and grumpy[i] is 1 if the owner is grumpy that minute (those customers leave unsatisfied), else 0. The owner may stay calm for exactly minutes consecutive minutes once, satisfying everyone in that window. Return the maximum number of satisfied customers.

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

Output16

Always satisfied = 1+1+1+7 = 10. Best 3-minute window (indices 5..7) saves 1+0+5 = 6 grumpy customers. 10 + 6 = 16.

customers (comma-separated)

grumpy (0/1, comma-separated)

minutes

def max_satisfied(customers, grumpy, minutes):
    base = sum(c for c, g in zip(customers, grumpy) if g == 0)
    win = 0
    best = 0
    for i in range(len(customers)):
        if grumpy[i] == 1:
            win += customers[i]
        if i >= minutes and grumpy[i - minutes] == 1:
            win -= customers[i - minutes]
        best = max(best, win)
    return base + best

function maxSatisfied(customers, grumpy, minutes) {
  let base = 0;
  for (let i = 0; i < customers.length; i++)
    if (grumpy[i] === 0) base += customers[i];
  let win = 0, best = 0;
  for (let i = 0; i < customers.length; i++) {
    if (grumpy[i] === 1) win += customers[i];
    if (i >= minutes && grumpy[i - minutes] === 1) win -= customers[i - minutes];
    best = Math.max(best, win);
  }
  return base + best;
}

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int base = 0;
        for (int i = 0; i < customers.length; i++)
            if (grumpy[i] == 0) base += customers[i];
        int win = 0, best = 0;
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 1) win += customers[i];
            if (i >= minutes && grumpy[i - minutes] == 1) win -= customers[i - minutes];
            best = Math.max(best, win);
        }
        return base + best;
    }
}

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
    int base = 0;
    for (int i = 0; i < (int)customers.size(); i++)
        if (grumpy[i] == 0) base += customers[i];
    int win = 0, best = 0;
    for (int i = 0; i < (int)customers.size(); i++) {
        if (grumpy[i] == 1) win += customers[i];
        if (i >= minutes && grumpy[i - minutes] == 1) win -= customers[i - minutes];
        best = max(best, win);
    }
    return base + best;
}

Explanation

Customers on non-grumpy minutes are always satisfied no matter what, so we add those up first into base. The only choice is where to place the one calm period of length minutes, and that period only helps on the grumpy minutes it covers.

So we slide a window of width minutes and, for each position, sum the customers on the grumpy minutes inside it — that is how many extra people the calm technique would save there. We keep the best such total in best.

The window slides cheaply: when minute i enters, we add customers[i] if it is grumpy, and when minute i - minutes leaves we subtract it if it was grumpy. The final answer is base + best.

Example: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3. The always-satisfied base is 1+1+1+7 = 10. The best 3-minute window (indices 5..7) saves 1+0+5 = 6 grumpy customers, so the total is 10 + 6 = 16.

Both the baseline and the sliding scan are single linear passes, so the whole solution is linear time.

Time: O(n) Space: O(1)