Grumpy Bookstore Owner [Medium] — Fixed Window Bonus

Problem Statement

customers[i] = customers at minute i. grumpy[i] = 1 if owner is grumpy. The owner can suppress grumpiness for minutes consecutive minutes. Maximize total satisfied customers.

Input: customers=[1,0,1,2,1,1,7,5], grumpy=[0,1,0,1,0,1,0,1], minutes=3
Output: 16

Intuition

Base satisfied = sum of customers when grumpy=0. Find fixed window of size minutes that adds the most extra (grumpy=1) customers.

Solutions

C++

int maxSatisfied(vector<int>& c, vector<int>& g, int min) {
    int base=0, extra=0, best=0;
    for(int i=0;i<c.size();i++) if(!g[i]) base+=c[i];
    for(int i=0;i<min;i++) if(g[i]) extra+=c[i];
    best=extra;
    for(int i=min;i<c.size();i++){
        if(g[i]) extra+=c[i];
        if(g[i-min]) extra-=c[i-min];
        best=max(best,extra);
    }
    return base+best;
}

Python

def maxSatisfied(customers: list[int], grumpy: list[int], minutes: int) -> int:
    base = sum(c for c,g in zip(customers,grumpy) if not g)
    extra = sum(c for c,g in zip(customers[:minutes], grumpy[:minutes]) if g)
    best = extra
    for i in range(minutes, len(customers)):
        extra += customers[i]*grumpy[i] - customers[i-minutes]*grumpy[i-minutes]
        best = max(best, extra)
    return base + best

Complexity

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