LeetCode 1052 - Grumpy Bookstore Owner

This problem asks us to maximize the number of satisfied customers in a bookstore over n minutes. We are given two arrays: customers, which indicates how many customers arrive each minute, and grumpy, which indicates whether the bookstore owner is grumpy (1) or not grumpy (0)…

leetcodemediumarraysliding-window

LeetCode Problem 1052

Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

Problem Understanding

This problem asks us to maximize the number of satisfied customers in a bookstore over n minutes. We are given two arrays: customers, which indicates how many customers arrive each minute, and grumpy, which indicates whether the bookstore owner is grumpy (1) or not grumpy (0) during each minute. If the owner is grumpy, the customers in that minute are not satisfied; otherwise, they are satisfied. Additionally, the owner can use a secret technique once to avoid being grumpy for minutes consecutive minutes.

The goal is to determine the maximum number of satisfied customers possible by strategically using this technique.

The constraints tell us that the input arrays can be as long as 20,000 elements, and each customer's count can be up to 1000. This suggests that an inefficient brute-force solution that examines all possible intervals of minutes could be too slow. Edge cases include scenarios where the owner is never grumpy, where minutes is equal to n, or where all customer counts are zero.

Approaches

Brute Force

A brute-force approach would consider every possible minutes-length interval where the owner could use the technique. For each interval, we would calculate the total number of satisfied customers: the sum of all customers during non-grumpy minutes plus the sum of all customers in the selected interval (which we convert from grumpy to non-grumpy). This approach is correct but inefficient because it requires calculating sums for up to n - minutes + 1 intervals, leading to a time complexity of O(n * minutes), which could be as high as 4 * 10^8 in the worst case.

Optimal Approach

The key insight is that the problem can be reduced to a sliding window problem. First, we compute the total number of customers already satisfied when the owner is not grumpy. Then, we slide a window of length minutes across the array, keeping track of the additional customers that could be satisfied if we applied the technique to that window. The maximum additional satisfied customers in any window, added to the initially satisfied customers, gives the answer. This approach runs in O(n) time because each element is processed exactly twice, once entering the window and once leaving it.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * minutes) O(1) Check every possible interval of length minutes
Optimal O(n) O(1) Sliding window approach to find maximum extra satisfied customers

Algorithm Walkthrough

  1. Initialize base_satisfied to store the number of customers already satisfied during non-grumpy minutes. Iterate over customers and grumpy arrays, adding customers[i] to base_satisfied if grumpy[i] is 0.
  2. Create a sliding window of length minutes. Initialize extra_satisfied to store the number of additional satisfied customers if the technique is applied. For the first minutes elements, add customers[i] to extra_satisfied only if grumpy[i] is 1.
  3. Initialize max_extra_satisfied to the value of extra_satisfied.
  4. Slide the window from index minutes to n-1. At each step, subtract the first element leaving the window from extra_satisfied (if it was a grumpy minute) and add the new element entering the window (if it is a grumpy minute). Update max_extra_satisfied if extra_satisfied exceeds it.
  5. The final result is base_satisfied + max_extra_satisfied.

Why it works: The invariant maintained is that at every step, extra_satisfied correctly counts the number of additional customers who can be satisfied in the current window of minutes. By checking all windows efficiently with a sliding window, we ensure that we find the maximum possible additional satisfied customers.

Python Solution

from typing import List

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        base_satisfied = 0
        for i in range(n):
            if grumpy[i] == 0:
                base_satisfied += customers[i]

        extra_satisfied = 0
        for i in range(minutes):
            if grumpy[i] == 1:
                extra_satisfied += customers[i]

        max_extra_satisfied = extra_satisfied

        for i in range(minutes, n):
            if grumpy[i - minutes] == 1:
                extra_satisfied -= customers[i - minutes]
            if grumpy[i] == 1:
                extra_satisfied += customers[i]
            max_extra_satisfied = max(max_extra_satisfied, extra_satisfied)

        return base_satisfied + max_extra_satisfied

Explanation: We first calculate customers who are satisfied without using the technique. Then, we use a sliding window of size minutes to compute the maximum additional customers that can be satisfied. At each step, the window efficiently updates the extra satisfied customers without recomputing sums from scratch.

Go Solution

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    n := len(customers)
    baseSatisfied := 0
    for i := 0; i < n; i++ {
        if grumpy[i] == 0 {
            baseSatisfied += customers[i]
        }
    }

    extraSatisfied := 0
    for i := 0; i < minutes; i++ {
        if grumpy[i] == 1 {
            extraSatisfied += customers[i]
        }
    }

    maxExtraSatisfied := extraSatisfied

    for i := minutes; i < n; i++ {
        if grumpy[i-minutes] == 1 {
            extraSatisfied -= customers[i-minutes]
        }
        if grumpy[i] == 1 {
            extraSatisfied += customers[i]
        }
        if extraSatisfied > maxExtraSatisfied {
            maxExtraSatisfied = extraSatisfied
        }
    }

    return baseSatisfied + maxExtraSatisfied
}

Go-specific notes: The logic is identical to Python, but we explicitly manage slice indices. There is no need for dynamic arrays or type hints, and integer arithmetic is safe given the constraints.

Worked Examples

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

  1. base_satisfied = 1 + 1 + 1 + 7 = 10
  2. Initial window [1,2,1] (indices 1-3), extra satisfied = 2 + 1 = 3
  3. Slide window right, extra satisfied updates:
  • [2,1,1] = 2 + 1 + 1 = 4
  • [1,1,7] = 1 + 1 + 0 = 2
  • [1,7,5] = 1 + 0 + 5 = 6 (max)

Result: 10 + 6 = 16

Example 2: customers = [1], grumpy = [0], minutes = 1

  • Base satisfied = 1
  • Sliding window does not increase satisfaction
  • Result = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed twice: once entering and once leaving the sliding window
Space O(1) Only a few integer variables are used; no extra data structures needed

The optimal solution scales linearly with the number of minutes the store is open, making it efficient for the maximum constraint of 20,000.

Test Cases

# Provided examples
assert Solution().maxSatisfied([1,0,1,2,1,1,7,5], [0,1,0,1,0,1,0,1], 3) == 16
assert Solution().maxSatisfied([1], [0], 1) == 1

# Edge cases
assert Solution().maxSatisfied([0,0,0], [1,1,1], 2) == 0  # no customers at all
assert Solution().maxSatisfied([1,2,3], [0,0,0], 2) == 6  # never grumpy
assert Solution().maxSatisfied([1,2,3], [1,1,1], 3) == 6  # always grumpy, use technique for all

# Mixed case
assert Solution().maxSatisfied([4,10,10], [1,0,1], 2) == 24  # choose window to maximize extra
Test Why
[1,0,1,2,1,1,7,5] Verifies typical case with mixed grumpy and non-grumpy
[1] Minimal input case
[0,0,0] No customers scenario
[1,2,3] Owner never grumpy
[1,2,3] Owner always grumpy, technique covers all
[4,10,10] Technique must be optimally applied

Edge Cases

Case 1: All customers zero

If all `customers[i] =