We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Grumpy Bookstore Owner

Number: 1138

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta, Microsoft, Walmart Labs, Apple, Nutanix

Problem Description

A bookstore owner has a store open for n minutes. Each minute, customers[i] customers enter and immediately leave after that minute. The owner is grumpy during some minutes (indicated by grumpy[i] == 1) and, as a result, customers during those minutes are unsatisfied. However, the owner can use a secret technique once to remain not grumpy for a consecutive block of "minutes" minutes, turning those potentially unsatisfied customers into satisfied ones. The task is to choose the best time window to maximize the total number of satisfied customers over the day.

Key Insights

  • The customers during minutes when the owner is not grumpy (grumpy[i] == 0) are always satisfied. Sum these as a base value.
  • Applying the secret technique makes unsatisfied customers during the chosen window become satisfied. So, for a window of length "minutes", only consider the additional gain from minutes when grumpy[i] == 1.
  • Use a sliding window of fixed size "minutes" over the array to calculate the potential extra gain.
  • The final answer is the sum of the base satisfied customers and the maximum extra gain obtained from any valid window.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array once for the base sum and then use a sliding window approach. Space Complexity: O(1) – Only constant extra space is used.

Solution

We first calculate the number of satisfied customers when the owner is not grumpy (base satisfaction). Then, we compute the additional gain if we were to suppress the owner's grumpiness for a consecutive block of "minutes" minutes. This is done by using a sliding window technique to sum the number of customers during grumpy minutes within each window and updating the maximum gain found. Finally, we add the base satisfaction to this maximum extra gain to get the result.

Code Solutions

# Python solution for Grumpy Bookstore Owner

def maxSatisfied(customers, grumpy, minutes):
    # Calculate the base satisfied customers where owner is not grumpy
    base_satisfaction = 0
    n = len(customers)
    for i in range(n):
        if grumpy[i] == 0:
            base_satisfaction += customers[i]
    
    # Calculate the additional gain for the first window of size 'minutes'
    extra_gain = 0
    for i in range(minutes):
        if grumpy[i] == 1:
            extra_gain += customers[i]
    
    max_extra_gain = extra_gain
    
    # Slide the window from minutes to n-1
    for i in range(minutes, n):
        # Remove the leftmost element if it was grumpy
        if grumpy[i - minutes] == 1:
            extra_gain -= customers[i - minutes]
        # Add the new element if it is grumpy
        if grumpy[i] == 1:
            extra_gain += customers[i]
        # Update max extra gain
        max_extra_gain = max(max_extra_gain, extra_gain)
    
    # Total satisfied customers is the base satisfaction plus the best extra gain obtained
    return base_satisfaction + max_extra_gain

# Example usage:
# customers = [1,0,1,2,1,1,7,5]
# grumpy = [0,1,0,1,0,1,0,1]
# minutes = 3
# print(maxSatisfied(customers, grumpy, minutes))  # Output should be 16
← Back to All Questions