{x}
blog image

Grumpy Bookstore Owner

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.

Solution Explanation: Grumpy Bookstore Owner

This problem involves maximizing customer satisfaction by strategically applying a "not grumpy" technique to a bookstore owner. The solution uses a sliding window approach for efficiency.

Understanding the Problem

We're given:

  • customers: An array representing the number of customers arriving each minute.
  • grumpy: A binary array indicating whether the owner is grumpy (1) or not (0) each minute.
  • minutes: The duration the owner can remain not grumpy using their technique.

The goal is to find the maximum number of satisfied customers achievable by applying the "not grumpy" technique to a single consecutive minutes-long interval.

Approach: Sliding Window

  1. Calculate Baseline Satisfaction: First, calculate the total number of satisfied customers without using the "not grumpy" technique. This is the sum of customers arriving when the owner is not grumpy (grumpy[i] == 0).

  2. Sliding Window for Grumpy Minutes: This is where the sliding window technique shines. We maintain a window of size minutes that slides across the grumpy array.

    • Window Sum: Within the window, we calculate the sum of customers (customers[i]) who are only dissatisfied because the owner is grumpy (grumpy[i] == 1).
    • Maximum Window Sum: As we slide the window, we keep track of the maximum sum of dissatisfied customers within any window. This represents the maximum number of additional satisfied customers we can achieve by applying the "not grumpy" technique to the best window.

  3. Combine Results: Finally, we add the baseline satisfaction (from step 1) and the maximum additional satisfied customers from the best window (from step 2) to get the final answer.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the customers and grumpy arrays. We iterate through the arrays once using the sliding window.
  • Space Complexity: O(1). We only use a few constant extra variables.

Code Examples (Python)

def maxSatisfied(customers, grumpy, minutes):
    """
    Finds the maximum number of satisfied customers using a sliding window.
 
    Args:
        customers: List of customer counts per minute.
        grumpy: List indicating grumpy status (0 or 1) per minute.
        minutes: Duration the owner can be not grumpy.
 
    Returns:
        The maximum number of satisfied customers.
    """
 
    n = len(customers)
    baseline_satisfied = sum(c for c, g in zip(customers, grumpy) if g == 0)  #Step 1
 
    max_additional_satisfied = 0
    window_sum = sum(c * g for c, g in zip(customers[:minutes], grumpy[:minutes])) # Step 2 - Initialize window sum
    max_additional_satisfied = window_sum # Step 2 - Initialize max additional satisfied
 
    for i in range(minutes, n):
        window_sum += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes]
        max_additional_satisfied = max(max_additional_satisfied, window_sum)
 
    return baseline_satisfied + max_additional_satisfied  #Step 3

This Python code directly implements the sliding window approach as described above. The other languages (Java, C++, Go, TypeScript, Rust) would follow a very similar structure, differing only in syntax and data structure handling. The core algorithm remains the same.