Problem Description

You are given a bookstore that is open for n minutes. During each minute, a certain number of customers enter and leave the store.

You have two arrays:

• customers[i]: the number of customers entering at minute i (they all leave after that minute ends)
• grumpy[i]: a binary value where 1 means the owner is grumpy at minute i, and 0 means they're not grumpy

When the owner is grumpy, customers entering during that minute are not satisfied. When the owner is not grumpy, customers are satisfied.

The owner has a special technique: they can force themselves to not be grumpy for exactly minutes consecutive minutes, but this technique can only be used once during the entire day.

Your task is to find the maximum number of satisfied customers possible by strategically using the technique at the optimal time.

For example, if customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], and minutes = 3:

• Without using the technique, satisfied customers = 1 (minute 0) + 1 (minute 2) + 1 (minute 4) + 7 (minute 6) = 10
• If we use the technique from minute 5 to 7, we can additionally satisfy 1 (minute 5) + 5 (minute 7) = 6 more customers
• Total maximum satisfied customers = 10 + 6 = 16

The goal is to determine where to apply the technique to maximize the total number of satisfied customers.

Intuition

Let's think about what happens when we use the special technique. The technique allows us to make the owner not grumpy for minutes consecutive minutes. This means we can "save" customers who would otherwise be unsatisfied during those grumpy minutes.

First, we can observe that there are some customers who are always satisfied - these are the customers who arrive when the owner is naturally not grumpy (when grumpy[i] = 0). These customers will be satisfied no matter where we apply our technique.

The key insight is that we want to use our technique during the window of time where we can "save" the most customers. In other words, we need to find the consecutive minutes where the most customers would be lost due to the owner being grumpy.

This naturally leads us to a sliding window approach:

1. Calculate the baseline satisfied customers (when grumpy[i] = 0)
2. Use a sliding window of size minutes to find where we can maximize the additional satisfied customers
3. The additional customers we can satisfy in any window are those where grumpy[i] = 1 within that window

For each possible window position, we calculate how many customers we could "save" by making the owner not grumpy during that period. The window that saves the most customers is where we should apply our technique.

The formula customers[i] * grumpy[i] gives us the number of unsatisfied customers at minute i (it's 0 when not grumpy, and customers[i] when grumpy). By finding the window with the maximum sum of this value, we find the optimal time to use the technique.

Learn more about Sliding Window patterns.

Solution Approach

The solution implements a sliding window technique to find the optimal time to use the special technique.

Step 1: Initialize the sliding window

We start by calculating the number of unsatisfied customers in the first window of size minutes:

mx = cnt = sum(c * g for c, g in zip(customers[:minutes], grumpy))

This gives us the initial window's unsatisfied customers. The expression c * g equals customers[i] when grumpy[i] = 1 and 0 when grumpy[i] = 0.

Step 2: Slide the window through the array

We then slide the window one position at a time from index minutes to the end:

for i in range(minutes, len(customers)):
    cnt += customers[i] * grumpy[i]
    cnt -= customers[i - minutes] * grumpy[i - minutes]
    mx = max(mx, cnt)

For each new position:

• Add the new element entering the window: customers[i] * grumpy[i]
• Remove the element leaving the window: customers[i - minutes] * grumpy[i - minutes]
• Update mx to track the maximum unsatisfied customers we can save

Step 3: Calculate the final result

The total satisfied customers equals:

return sum(c * (g ^ 1) for c, g in zip(customers, grumpy)) + mx

This consists of two parts:

• sum(c * (g ^ 1) for c, g in zip(customers, grumpy)): The baseline satisfied customers (when the owner is naturally not grumpy). The XOR operation g ^ 1 flips the grumpy value, so we get 1 when not grumpy and 0 when grumpy.
• mx: The maximum additional customers we can satisfy by using the technique optimally.

The time complexity is O(n) where n is the length of the arrays, and the space complexity is O(1) as we only use a few variables to track the window state.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• customers = [1, 0, 1, 2, 1, 1, 7, 5]
• grumpy = [0, 1, 0, 1, 0, 1, 0, 1]
• minutes = 3

Step 1: Calculate unsatisfied customers in the first window (indices 0-2)

For the first window covering minutes 0, 1, and 2:

• Minute 0: customers[0] * grumpy[0] = 1 * 0 = 0 (not grumpy, so 0 unsatisfied)
• Minute 1: customers[1] * grumpy[1] = 0 * 1 = 0 (grumpy but no customers)
• Minute 2: customers[2] * grumpy[2] = 1 * 0 = 0 (not grumpy, so 0 unsatisfied)

Initial window sum: cnt = 0 + 0 + 0 = 0 Maximum so far: mx = 0

Step 2: Slide the window through remaining positions

Window at indices 1-3:

• Remove minute 0: cnt -= 1 * 0 = 0
• Add minute 3: cnt += 2 * 1 = 2
• New cnt = 0 - 0 + 2 = 2
• Update mx = max(0, 2) = 2

Window at indices 2-4:

• Remove minute 1: cnt -= 0 * 1 = 0
• Add minute 4: cnt += 1 * 0 = 0
• New cnt = 2 - 0 + 0 = 2
• mx = max(2, 2) = 2

Window at indices 3-5:

• Remove minute 2: cnt -= 1 * 0 = 0
• Add minute 5: cnt += 1 * 1 = 1
• New cnt = 2 - 0 + 1 = 3
• Update mx = max(2, 3) = 3

Window at indices 4-6:

• Remove minute 3: cnt -= 2 * 1 = 2
• Add minute 6: cnt += 7 * 0 = 0
• New cnt = 3 - 2 + 0 = 1
• mx = max(3, 1) = 3

Window at indices 5-7:

• Remove minute 4: cnt -= 1 * 0 = 0
• Add minute 7: cnt += 5 * 1 = 5
• New cnt = 1 - 0 + 5 = 6
• Update mx = max(3, 6) = 6

Step 3: Calculate total satisfied customers

Baseline satisfied customers (when naturally not grumpy):

• Minute 0: 1 * (0 ^ 1) = 1 * 1 = 1
• Minute 1: 0 * (1 ^ 1) = 0 * 0 = 0
• Minute 2: 1 * (0 ^ 1) = 1 * 1 = 1
• Minute 3: 2 * (1 ^ 1) = 2 * 0 = 0
• Minute 4: 1 * (0 ^ 1) = 1 * 1 = 1
• Minute 5: 1 * (1 ^ 1) = 1 * 0 = 0
• Minute 6: 7 * (0 ^ 1) = 7 * 1 = 7
• Minute 7: 5 * (1 ^ 1) = 5 * 0 = 0

Baseline sum: 1 + 0 + 1 + 0 + 1 + 0 + 7 + 0 = 10

Final result: 10 + 6 = 16

The optimal strategy is to use the technique during minutes 5-7, which saves 6 additional customers (1 from minute 5 and 5 from minute 7), giving us a total of 16 satisfied customers.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array customers. The algorithm performs the following operations:

• Initial calculation of the first window takes O(minutes) time
• The sliding window loop runs from index minutes to n-1, performing O(1) operations in each iteration, resulting in O(n - minutes) time
• The final sum calculation iterates through all elements once, taking O(n) time
• Overall: O(minutes) + O(n - minutes) + O(n) = O(n)

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables mx and cnt, regardless of the input size. The zip operations and iterations don't create additional data structures that scale with input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Window Calculation

A common mistake is incorrectly calculating what the sliding window represents. The window should track unsatisfied customers that can be made satisfied, not all customers in the window.

Incorrect approach:

# Wrong: This counts ALL customers in the window
window_sum = sum(customers[i] for i in range(minutes))

Correct approach:

# Right: Only count customers when the owner IS grumpy
window_sum = sum(customers[i] * grumpy[i] for i in range(minutes))

2. Off-by-One Error in Window Sliding

Another pitfall is incorrectly managing the window boundaries when sliding, especially when removing the element that's leaving the window.

Incorrect approach:

# Wrong: Using wrong index for the element leaving the window
for i in range(minutes, len(customers)):
    cnt += customers[i] * grumpy[i]
    cnt -= customers[i - minutes + 1] * grumpy[i - minutes + 1]  # Wrong offset!

Correct approach:

# Right: Proper index calculation
for i in range(minutes, len(customers)):
    cnt += customers[i] * grumpy[i]
    cnt -= customers[i - minutes] * grumpy[i - minutes]  # Correct offset

3. Forgetting Edge Cases

Failing to handle edge cases where minutes equals or exceeds the array length.

Solution: Add validation:

if minutes >= len(customers):
    # If we can make the owner not grumpy for the entire day
    return sum(customers)

4. Incorrect Base Satisfaction Calculation

Computing the baseline satisfied customers incorrectly by not properly inverting the grumpy values.

Incorrect approach:

# Wrong: This counts customers when grumpy, not when satisfied
base = sum(c * g for c, g in zip(customers, grumpy))

Correct approach:

# Right: Count customers when NOT grumpy (grumpy == 0)
base = sum(c * (g ^ 1) for c, g in zip(customers, grumpy))
# Or alternatively:
base = sum(c for c, g in zip(customers, grumpy) if g == 0)