#1052

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Grumpy Bookstore Owner

Maximize satisfied customers in a bookstore by strategically suppressing the owner's grumpy minutes using a sliding window approach.

array sliding window

Problem Statement

You are managing a bookstore where the owner can be grumpy at certain minutes. Given an array customers representing the number of customers entering each minute and a binary array grumpy indicating when the owner is grumpy, calculate the maximum number of satisfied customers. A customer is satisfied if the owner is not grumpy during that minute or if the owner uses a secret technique to suppress grumpiness for a consecutive period of 'minutes'.

Implement an algorithm that determines the optimal time interval for the owner to suppress grumpiness to maximize satisfied customers. Return the total maximum satisfied customers possible after applying this sliding window technique over the grumpy intervals.

Examples

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

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

Example details omitted.

Constraints

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

Solution Approach

Compute base satisfaction

Iterate through all minutes and sum customers[i] where grumpy[i] == 0. This represents customers already satisfied without using the owner's special technique.

Apply sliding window over grumpy intervals

Use a window of length 'minutes' and slide it across the array. For each window, sum customers[i] where grumpy[i] == 1. Keep track of the window that yields the maximum additional satisfied customers.

Combine results for final answer

Add the maximum extra satisfied customers from the sliding window to the base satisfaction. Return this sum as the total maximum satisfied customers achievable.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each minute is visited once for base calculation and once during sliding window. Space complexity is O(1) since calculations are done in-place without extra data structures beyond counters.

What Interviewers Usually Probe

Expecting you to recognize that non-grumpy minutes can be counted immediately.
Looking for sliding window implementation to optimize consecutive grumpy intervals.
Checking if you correctly combine base satisfaction with maximum gain from the window.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include base satisfied customers from non-grumpy minutes.
Incorrectly summing customers in sliding window due to off-by-one errors.
Sliding the window beyond array bounds or miscalculating potential gain.

Follow-up variants

Varying the length of the grumpy suppression window to see different maximums.
Handling large arrays with maximum customer counts to test O(n) efficiency.
Extending the problem to multiple intervals where grumpiness can be suppressed multiple times.

FAQ

What is the best approach to solve Grumpy Bookstore Owner?

Use a sliding window of size 'minutes' to maximize extra satisfied customers during grumpy periods, adding it to the base satisfaction.

Can I solve this problem without a sliding window?

Brute force is possible but inefficient; the sliding window reduces time complexity from O(n*minutes) to O(n).

How do I handle edge cases like all non-grumpy or all grumpy minutes?

Sum all customers for non-grumpy minutes as base. For all grumpy, apply the sliding window across the entire array to find maximum gain.

Why is this problem categorized under Array and Sliding Window?

Because it requires maintaining a running sum of customers over a consecutive interval within an array, updating efficiently as the window moves.

How do I calculate the total satisfied customers efficiently?

Compute base satisfaction from non-grumpy minutes, then slide a window over grumpy minutes to find maximum additional satisfied customers, summing both for the total.

terminal

Solution

Solution 1: Sliding Window

According to the problem description, we only need to count the number of customers when the boss is not angry $tot$, and add the maximum number of customers when the boss is angry within a sliding window of size `minutes` $mx$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxSatisfied(
        self, customers: List[int], grumpy: List[int], minutes: int
    ) -> int:
        mx = cnt = sum(c * g for c, g in zip(customers[:minutes], grumpy))
        for i in range(minutes, len(customers)):
            cnt += customers[i] * grumpy[i]
            cnt -= customers[i - minutes] * grumpy[i - minutes]
            mx = max(mx, cnt)
        return sum(c * (g ^ 1) for c, g in zip(customers, grumpy)) + mx

Continue Practicing

#1040 moving stones until consecutive ii #1031 maximum sum of two non overlapping subarrays #1004 max consecutive ones iii