1052. Grumpy Bookstore Owner

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

On some 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 of that minute are not satisfied, otherwise, they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for minutes consecutive minutes, but can only use it 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.

Approach 01:

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int total_satisfied = 0;
        int additional_satisfied = 0;
        int current_window_satisfied = 0;

        for (int i = 0; i < customers.size(); ++i) {
            if (grumpy[i] == 0){
                total_satisfied += customers[i];
            }
            else{
                current_window_satisfied += customers[i];
            }
            if (i >= X && grumpy[i - X] == 1){
                current_window_satisfied -= customers[i - X];
            }
            additional_satisfied = max(additional_satisfied, current_window_satisfied);
        }

        return total_satisfied + additional_satisfied;
    }
};

from typing import List

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        # Calculate the total number of satisfied customers without any changes
        total_satisfied = sum(c for i, c in enumerate(customers) if grumpy[i] == 0)
        additional_satisfied = 0
        current_window_satisfied = 0

        # Iterate over all customers
        for i, customer in enumerate(customers):
            # Add to the current window satisfied if the owner is grumpy
            if grumpy[i] == 1:
                current_window_satisfied += customer
            # Remove from the current window if the start of the window was grumpy
            if i >= X and grumpy[i - X] == 1:
                current_window_satisfied -= customers[i - X]
            # Update the maximum number of customers that can be satisfied
            additional_satisfied = max(additional_satisfied, current_window_satisfied)

        # Return the total satisfied customers
        return total_satisfied + additional_satisfied

Time Complexity

The time complexity of the given code is O(n), where nnn is the number of elements in the customers vector. Here’s the breakdown:

1. Initialization:

   • Initializing variables (total_satisfied, additional_satisfied, current_window_satisfied) takes constant time, O(1).

2. Single Pass Through Customers:

   • The for loop iterates over each element of the customers vector exactly once, resulting in O(n) time complexity.
   • Inside the loop, each operation (including checking conditions, updating sums, and computing the maximum) takes constant time, O(1).

Since the loop runs in linear time and the operations within the loop are constant time, the overall time complexity is O(n).

Space Complexity

The space complexity of the given code is O(1), as it uses a fixed amount of extra space regardless of the input size. Here’s the breakdown:

1. Variables:

   • The variables total_satisfied, additional_satisfied, and current_window_satisfied use constant space.

2. No Additional Data Structures:

   • The code does not use any additional data structures that grow with the input size.

Therefore, the space complexity is O(1).