Grumpy Bookstore Owner

Medium
788.

Grumpy Bookstore Owner

Grumpy Bookstore Owner is a medium coding problem on arrays and sliding window, asked in Amazon, Google, Nutanix and Swiggy interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} customers
 * @param {number[]} grumpy
 * @param {number} minutes
 * @return {number}
 */
var maxSatisfied = function(customers, grumpy, minutes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Grumpy Bookstore Owner — Solution in Python, Java & C++

Grumpy Bookstore Owner solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Grumpy Bookstore Owner is a medium coding problem on arrays and sliding window, asked in Amazon, Google, Nutanix and Swiggy interviews.

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

Hints for Grumpy Bookstore Owner

  1. Hint 1

    The customers in non-grumpy minutes are satisfied no matter what — that part is fixed.

  2. Hint 2

    The technique only converts customers in minutes where the owner is grumpy.

  3. Hint 3

    So maximise the grumpy-minute customers inside one window of minutes length.

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

Java

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

C++

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
    int n = (int) customers.size(), base = 0;
    for (int i = 0; i < n; i++) if (grumpy[i] == 0) base += customers[i];
    int gain = 0;
    for (int i = 0; i < minutes && i < n; i++) if (grumpy[i] == 1) gain += customers[i];
    int best = gain;
    for (int i = minutes; i < n; i++) {
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sliding Window Technique