Scale Engineer

Grumpy Bookstore Owner

Med
#1004Time: O(N * M), where N is the length of the `customers` array and M is the `minutes` value. The outer loop runs `N - M + 1` times, and the inner loop runs `M` times. In the worst case, `M` can be close to `N`, leading to O(N^2) complexity.Space: O(1), as we only use a few variables to store the sums and maximums.1 company
Patterns
Sliding Window
Data structures
Array
Companies
Nutanix

Prompt

There is a bookstore owner that has a store open for n minutes. You are given an integer array customers of length n where customers[i] is the number of the customers that enter the store at the start of the ith minute and all those customers leave after the end of that minute.

During certain minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.

When the bookstore owner is grumpy, the customers entering during that minute are not satisfied. Otherwise, they are satisfied.

The bookstore owner knows a secret technique to remain not grumpy for minutes consecutive minutes, but this technique can only be used once.

Return the maximum number of customers that can be satisfied throughout the day.

 

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:

The bookstore owner keeps themselves not grumpy for the last 3 minutes.

The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Example 2:

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

Output: 1

 

Constraints:

  • n == customers.length == grumpy.length
  • 1 <= minutes <= n <= 2 * 104
  • 0 <= customers[i] <= 1000
  • grumpy[i] is either 0 or 1.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible continuous window of minutes length. For each window, we calculate the total number of satisfied customers if the owner uses their special technique during that time. We then keep track of the maximum satisfaction score found across all possible windows.

Algorithm

  • Initialize maxTotalSatisfied to 0.
  • Iterate through all possible starting positions for the minutes-long window, from i = 0 to n - minutes.
  • For each starting position i, calculate the total number of satisfied customers if the technique is applied to the window [i, i + minutes - 1].
    • Initialize currentTotalSatisfied to 0.
    • Iterate through all minutes j from 0 to n-1.
    • If minute j is within the technique window (j >= i and j < i + minutes), add customers[j] to currentTotalSatisfied.
    • Otherwise, if the owner is not grumpy (grumpy[j] == 0), add customers[j] to currentTotalSatisfied.
  • Update maxTotalSatisfied = max(maxTotalSatisfied, currentTotalSatisfied).
  • After checking all windows, return maxTotalSatisfied.

Walkthrough

The core idea is to simulate using the technique for every possible start time. A window of minutes can start at any index i from 0 to n - minutes, where n is the total number of minutes.

For each starting index i, we define a window from i to i + minutes - 1. We then calculate the total satisfied customers for this specific choice. A simpler way to structure the calculation is to first find the baseline satisfaction (customers satisfied without the technique). Then, for each window, calculate the additional customers gained and add it to the baseline. The goal is to find the window that provides the maximum additional gain.

We iterate through all possible windows, calculate the gain for each, and find the maximum possible total satisfaction.

class Solution {    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {        int n = customers.length;        int initiallySatisfied = 0;        for (int i = 0; i < n; i++) {            if (grumpy[i] == 0) {                initiallySatisfied += customers[i];            }        }         int maxExtraSatisfied = 0;        // Iterate through all possible windows        for (int i = 0; i <= n - minutes; i++) {            int currentExtraSatisfied = 0;            // Calculate the gain for the current window            for (int j = i; j < i + minutes; j++) {                if (grumpy[j] == 1) {                    currentExtraSatisfied += customers[j];                }            }            maxExtraSatisfied = Math.max(maxExtraSatisfied, currentExtraSatisfied);        }         return initiallySatisfied + maxExtraSatisfied;    }}

Complexity

Time

O(N * M), where N is the length of the `customers` array and M is the `minutes` value. The outer loop runs `N - M + 1` times, and the inner loop runs `M` times. In the worst case, `M` can be close to `N`, leading to O(N^2) complexity.

Space

O(1), as we only use a few variables to store the sums and maximums.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem statement's logic.

Cons

  • Inefficient due to nested loops, leading to redundant calculations.

  • The time complexity of O(N * M) can be too slow for large inputs, potentially causing a 'Time Limit Exceeded' error.

Solutions

class Solution {public  int maxSatisfied(int[] customers, int[] grumpy, int minutes) {    int s = 0, cs = 0;    int n = customers.length;    for (int i = 0; i < n; ++i) {      s += customers[i] * grumpy[i];      cs += customers[i];    }    int t = 0, ans = 0;    for (int i = 0; i < n; ++i) {      t += customers[i] * grumpy[i];      int j = i - minutes + 1;      if (j >= 0) {        ans = Math.max(ans, cs - (s - t));        t -= customers[j] * grumpy[j];      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem