Grumpy Bookstore Owner

Q: What is the time complexity of Grumpy Bookstore Owner?

O(n). The solution iterates through the customers array once, updating sums and sliding the window in constant time per iteration, resulting in linear time complexity.

Q: What pattern does Grumpy Bookstore Owner use?

The Pattern: Sliding Window (Fixed-Size Window Sum Optimization) The Heuristic: When needing to find the maximum sum of a subarray of fixed length under certain conditions, use a sliding window to add the new element and remove the oldest element efficiently, avoiding recomputation and achieving O(n) time.

Medium Sliding Window

Problem

Given arrays customers and grumpy of equal length and an integer minutes, return the maximum number of customers that can be satisfied by using a secret technique to keep the owner not grumpy for a continuous window of length minutes.

1 ≤ customers.length == grumpy.length ≤ 20000
0 ≤ customers[i] ≤ 1000
grumpy[i] is 0 or 1
1 ≤ minutes ≤ customers.length

Example

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

Output: 16

Initially, customers satisfied without the technique are those at indices where grumpy[i] == 0: indices 0, 2, 4, 6, totaling 1 + 1 + 1 + 7 = 10. The technique can be applied to a window of length 3 to convert grumpy minutes to non-grumpy. Applying it from index 5 to 7 covers grumpy minutes at indices 5 and 7, adding customers[5] + customers[7] = 1 + 5 = 6 more satisfied customers. The total maximum satisfied customers is 10 + 6 = 16.

Approach

Straightforward Solution

A brute-force approach would consider every possible window of length minutes, summing the customers during grumpy minutes in that window and adding the customers during non-grumpy minutes outside the window. This approach is O(n * minutes), which is inefficient for large inputs.

Core Observation

The total satisfied customers equals the sum of customers during non-grumpy minutes plus the maximum additional customers that can be gained by applying the technique to a continuous window of length minutes covering grumpy minutes.

Path to Optimal

Preview

The key insight is to separate the problem into two parts: (1) sum of customers during non-grumpy minutes (fixed), and (2) maximum sum of customers during grumpy minutes in any window of length minutes…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the arrays once, accumulating the base satisfied customers from non-grumpy minutes. Simultaneously, maintain a sliding window of size minutes over the grumpy minutes to track the extra customers that can be gained by applying the technique…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The solution iterates through the customers array once, updating sums and sliding the window in constant time per iteration, resulting in linear time complexity.

Space

O(1)

Only a fixed number of integer variables are used to track sums and indices, so the auxiliary space is constant regardless of input size.

Pattern Spotlight

Sliding Window (Fixed-Size Window Sum Optimization)

When needing to find the maximum sum of a subarray of fixed length under certain conditions, use a sliding window to add the new element and remove the oldest element efficiently, avoiding recomputation and achieving O(n) time.

Solution

Python

1class Solution:
  def maxSatisfied(self, customers: list[int], grumpy: list[int], minutes: int) -> int:
      base = 0
      extra = 0
      best_extra = 0
6
      for i in range(len(customers)):
          if grumpy[i] == 0:
              base += customers[i]
          else:
              extra += customers[i]
12
          if i >= minutes and grumpy[i - minutes] == 1:
              extra -= customers[i - minutes]
15
          if i >= minutes - 1:
              best_extra = max(best_extra, extra)
18
      return base + best_extra

Step-by-Step Solution

Accumulate Base Satisfaction and Track Extra Customers with Sliding Window

3base = 0
4extra = 0
5best_extra = 0
7for i in range(len(customers)):
8    if grumpy[i] == 0:
9        base += customers[i]
10    else:
11        extra += customers[i]
13    if i >= minutes and grumpy[i - minutes] == 1:
14        extra -= customers[i - minutes]
16    if i >= minutes - 1:
17        best_extra = max(best_extra, extra)

Objective

To compute the total customers satisfied without the technique and simultaneously track the extra customers gained by applying the technique over a sliding window of length minutes.

Key Insight

Separating customers into those satisfied regardless of grumpiness and those only satisfied if the technique is applied allows efficient calculation. The sliding window accumulates extra customers from grumpy minutes within the current window by adding the new element and removing the element that falls out of the window, maintaining the sum in O(1) time per iteration. This approach avoids recomputing sums for every window, reducing complexity from O(n*minutes) to O(n).

Interview Quick-Check

Core Logic

The algorithm maintains two sums: 'base' for customers satisfied without the technique and 'extra' for customers satisfied by applying the technique in the current window, updating 'extra' efficiently using a sliding window.

State & Boundaries

The sliding window starts accumulating extra customers only after the first 'minutes' elements, ensuring the window size is fixed.

Common Pitfalls & Bugs

Forgetting to subtract the customer count leaving the window when sliding causes incorrect extra sums and wrong results.

Complexity

This single-pass approach achieves O(n) time and O(1) space, optimal for the problem constraints.

Return Maximum Total Satisfied Customers

To combine the base satisfied customers and the best extra customers from the sliding window to produce the final maximum satisfaction count.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 14 Critical

extra -= customers[i - minutes]

Subtract customers leaving the sliding window if that minute was grumpy.

This line's placement is critical to maintain the sliding window's fixed size and correct sum by removing the contribution of the minute that falls out, ensuring the extra customers count reflects only the current window.

Line 17 Critical

best_extra = max(best_extra, extra)

Update the best extra customers if the current window sum is greater.

This max operation is the core of the sliding window optimization, capturing the best possible extra gain by comparing the current window's extra customers to the best found so far.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why is it sufficient to consider only a single sliding window of length minutes to maximize the extra satisfied customers?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Grumpy Bookstore Owner from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Grumpy Bookstore Owner drill

or drill a free problem

1	`class Solution:`
2	`def maxSatisfied(self, customers: list[int], grumpy: list[int], minutes: int) -> int:`
3	`base = 0`
4	`extra = 0`
5	`best_extra = 0`
6
7	`for i in range(len(customers)):`
8	`if grumpy[i] == 0:`
9	`base += customers[i]`
10	`else:`
11	`extra += customers[i]`
12
13	`if i >= minutes and grumpy[i - minutes] == 1:`
14	`extra -= customers[i - minutes]`
15
16	`if i >= minutes - 1:`
17	`best_extra = max(best_extra, extra)`
18
19	`return base + best_extra`

3	`base = 0`
4	`extra = 0`
5	`best_extra = 0`
7	`for i in range(len(customers)):`
8	`if grumpy[i] == 0:`
9	`base += customers[i]`
10	`else:`
11	`extra += customers[i]`
13	`if i >= minutes and grumpy[i - minutes] == 1:`
14	`extra -= customers[i - minutes]`
16	`if i >= minutes - 1:`
17	`best_extra = max(best_extra, extra)`