# Grumpy Bookstore Owner
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/grumpy-bookstore-owner)
Canonical: https://scaleengineer.com/dsa/problems/grumpy-bookstore-owner
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix)
---
## Problem
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
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Sliding Window Optimization
This approach improves upon the brute-force method by avoiding redundant calculations. We can think of the problem as finding a window of size `minutes` that maximizes the number of customers who were initially unsatisfied. A sliding window technique is perfect for this. We calculate the sum for the first window and then slide it one position at a time, updating the sum in constant time by subtracting the element that leaves the window and adding the element that enters.
**Time:** O(N), where N is the length of the `customers` array. We perform a few separate passes over the array (one for initial satisfaction, one for the first window, and one for sliding), but each pass is linear. The total time is O(N) + O(M) + O(N-M), which simplifies to O(N). · **Space:** O(1), as we only use a few variables to store the running sums and maximums.
**Pros:** Highly efficient with a linear time complexity.; Avoids redundant calculations by reusing the sum from the previous window.; Optimal solution for this problem.
**Cons:** Slightly more complex to reason about than the straightforward brute-force approach.
### Explanation
The total number of satisfied customers is the sum of two parts:
1.  Customers who are satisfied regardless of the technique (when `grumpy[i] == 0`).
2.  The maximum number of extra customers we can satisfy by using the technique on a window of `minutes`. This is the maximum sum of `customers[i]` for `grumpy[i] == 1` in any window of size `minutes`.

First, we pre-calculate the total number of customers who are satisfied without any special technique. Then, we use a sliding window of size `minutes` to find the maximum gain possible. We initialize the window to cover the first `minutes` and calculate the 'extra satisfaction' gained. Then, we slide the window one step to the right, updating the sum by subtracting the leaving element's contribution and adding the entering element's contribution. We repeat this until the window reaches the end, keeping track of the maximum gain seen.

Finally, we add this maximum gain to the initially satisfied customer count.

```java
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int n = customers.length;
        int initiallySatisfied = 0;

        // Calculate the number of customers satisfied without the technique
        for (int i = 0; i < n; i++) {
            if (grumpy[i] == 0) {
                initiallySatisfied += customers[i];
            }
        }

        // Calculate the extra customers gained in the first window
        int currentExtraSatisfied = 0;
        for (int i = 0; i < minutes; i++) {
            if (grumpy[i] == 1) {
                currentExtraSatisfied += customers[i];
            }
        }

        int maxExtraSatisfied = currentExtraSatisfied;

        // Slide the window from the start to the end of the array
        for (int i = minutes; i < n; i++) {
            // Add the new element entering the window
            if (grumpy[i] == 1) {
                currentExtraSatisfied += customers[i];
            }
            // Remove the old element leaving the window
            if (grumpy[i - minutes] == 1) {
                currentExtraSatisfied -= customers[i - minutes];
            }
            // Update the maximum extra satisfied customers found so far
            maxExtraSatisfied = Math.max(maxExtraSatisfied, currentExtraSatisfied);
        }

        return initiallySatisfied + maxExtraSatisfied;
    }
}
```
### Algorithm
- First, calculate the base number of satisfied customers. Initialize `initiallySatisfied = 0`. Iterate from `i = 0` to `n-1`. If `grumpy[i] == 0`, add `customers[i]` to `initiallySatisfied`.
- The goal is now to find the window of size `minutes` that contains the maximum number of customers who were initially unsatisfied.
- Initialize a sliding window for the first `minutes`. Calculate the extra customers gained in this window (`currentExtraSatisfied`) by summing `customers[i]` where `grumpy[i] == 1` for `i` from `0` to `minutes - 1`.
- Initialize `maxExtraSatisfied = currentExtraSatisfied`.
- Slide the window one position at a time from `i = minutes` to `n-1`.
  - In each step, update `currentExtraSatisfied` by adding the new element entering the window (`customers[i]`) if it was a grumpy minute, and subtracting the element leaving the window (`customers[i - minutes]`) if it was a grumpy minute.
  - Update `maxExtraSatisfied = max(maxExtraSatisfied, currentExtraSatisfied)`.
- The final result is `initiallySatisfied + maxExtraSatisfied`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int minutes) {
    int s = 0, cs = 0;
    int n = customers.size();
    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 = max(ans, cs - (s - t));
        t -= customers[j] * grumpy[j];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int: s = sum(a * b for a, b in zip(customers, grumpy)) cs = sum(customers) t = ans = 0 for i, (a, b) in enumerate(zip(customers, grumpy), 1): t += a * b if (j: = i - minutes) >= 0: ans = max(ans, cs - (s - t)) t -= customers[j] * grumpy[j] return ans

```