Get started

Grumpy Bookstore Owner — Medium Problem & Solution

In minute i, customers[i] people visit the store and leave at the end of that minute.

  • Difficulty: Medium
  • Topics: Arrays, Sliding Window
  • Asked at: Amazon, Google, Swiggy
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In minute i, customers[i] people visit the store and leave at the end of that minute. If grumpy[i] is 1 the owner is grumpy and all of them leave unsatisfied; otherwise they all leave satisfied.

The owner may stay calm for minutes consecutive minutes, once. Return the maximum number of satisfied customers.

Example 1

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16
Explanation: Staying calm over the last three minutes saves the 5.

Example 2

Input: customers = [1], grumpy = [0], minutes = 1
Output: 1

Example 3

Input: customers = [4,10,10], grumpy = [1,1,0], minutes = 2
Output: 24

Constraints

  • 1 <= minutes <= customers.length <= 20000
  • 0 <= customers[i] <= 1000
  • grumpy[i] is 0 or 1

How to solve Grumpy Bookstore Owner

Split the answer into a fixed part and a window part. The fixed part is everyone arriving in a calm minute; the window part is the best block of minutes consecutive grumpy-minute customers that the technique can rescue.

Approach

  1. Sum customers[i] over every i with grumpy[i] == 0 — that is the baseline.
  2. Build the first window's rescue total: customers[i] over i < minutes with grumpy[i] == 1.
  3. Slide the window, adding the entering minute's customers when grumpy and subtracting the leaving minute's when it was.
  4. Return baseline plus the largest rescue seen.

Why it works

Applying the technique never loses a customer, and it only affects minutes inside the chosen window, so the two parts are independent and the total is the baseline plus the window's grumpy total. Maximising a fixed-size window sum is the standard roll.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Adding calm-minute customers into the window total double-counts them.
  • minutes may equal the whole array, in which case the sliding loop never runs — the initial window is the answer.
  • The total reaches 2 · 10^7, comfortably inside int.

Reference solution

Python

from typing import List

def maxSatisfied(customers: List[int], grumpy: List[int], minutes: int) -> int:
    n = len(customers)
    base = sum(c for c, g in zip(customers, grumpy) if g == 0)
    gain = sum(customers[i] for i in range(min(minutes, n)) if grumpy[i] == 1)
    best = gain
    for i in range(minutes, n):
        if grumpy[i] == 1:
            gain += customers[i]
        if grumpy[i - minutes] == 1:
            gain -= customers[i - minutes]
        best = max(best, gain)
    return base + best

JavaScript

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

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue