Domain 2MediumMEDIUM

Grumpy Bookstore Owner

LeetCode problem 1052: Grumpy Bookstore Owner (medium).

Domain: medium•Updated: 2026-09-07
#Array#Sliding Window

Problem Breakdown

We are given an array representing the number of customers entering per minute and a binary array indicating if the owner is grumpy at that specific minute (1 for grumpy, 0 otherwise). The goal is to maximize total satisfied customers by using a secret technique exactly once. This technique allows us to suppress “grumpiness” (make it effectively 0) for a contiguous duration of X minutes.

Inputs:

  • customers: List of integers representing customer count per minute.
  • grumpy: Binary list indicating grumpiness status (1 or 0).
  • X: Integer length of the window where we can apply the technique (make owner not grumpy).

Output:

  • An integer: The maximum number of satisfied customers possible.

Constraints & Edge Cases to Consider:

  • Lengths: Arrays are up to 20,000 elements; X is between 1 and array length. This suggests an O(N)O(N) or O(Nlog⁡N)O(N \log N) solution is required (avoiding quadratic time).
  • Values: Customer counts can be zero. Grumpiness is strictly binary. No negative values exist per constraints, but logic should handle 0 gracefully.
  • Overflow: Python handles large integers automatically, so standard sum accumulation won’t overflow 32-bit limits even if the total exceeds 231−12^{31}-1. However, in languages like Java/C++, we would need to ensure sums fit within integer types (though max possible here is ≈2×107\approx 2 \times 10^7, which fits easily).
  • Window Coverage: If X equals the array length, the technique covers everything. The logic should naturally handle this without special casing if implemented correctly via sliding window.

Intuition

Let’s start with a naive approach to understand what we are optimizing for. A brute force solution would iterate through every possible starting position of the X-minute window (there are N−X+1N-X+1 such windows). For each window, we calculate:

  1. The customers satisfied naturally outside this window (grumpy[i] == 0).
  2. Plus all customers inside the chosen window (since they become satisfied due to the technique).

Why Brute Force is Insufficient: Calculating the sum for every possible window naively takes O(X)O(X) per position, leading to an overall time complexity of O(N⋅X)O(N \cdot X). Given constraints where both can be up to 20,000, this could approach 4×1084 \times 10^8 operations in worst-case scenarios (e.g., X is large), which risks Time Limit Exceeded.

Key Insight: We can decompose the total satisfied customers into two independent parts:

  1. Base Satisfaction: Customers who are already satisfied because the owner isn’t grumpy (grumpy[i] == 0). This count never changes regardless of where we apply our technique, as those minutes remain non-grumpy naturally or stay within a window (where they don’t add extra value). We can calculate this sum once.
  2. Potential Gain: The additional customers satisfied by applying the technique on grumpy minutes (grumpy[i] == 1).

The problem transforms into: Find the contiguous subarray of length X that contains the maximum number of “lost” (unsatisfied) customers due to grumpiness, and add this sum to our Base Satisfaction. This is a classic Sliding Window pattern where we only care about values inside the window when they contribute to gain.

Approach

  1. Calculate Base Satisfaction: Iterate through customers once. Sum up all customers[i] where grumpy[i] == 0.
  2. Initialize Sliding Window for Gain: Create a variable (e.g., current_gain) initialized to the sum of customers in the first window [0, X-1] only if they are grumpy (grumpy[i] == 1).
  3. Slide the Window: Iterate from index i = X up to N - 1.
    • Add the new element entering the window (at i) to gain only if it is a grumpy minute.
    • Remove the old element leaving the window (at i - X) from gain only if it was a grumpy minute.
  4. Track Maximum: Keep updating a variable (max_gain) with the maximum value of current_gain seen during the slide.
  5. Final Result: Return base_satisfaction + max_gain.

Complexity Analysis

  • Time Complexity: O(N)O(N)
    • We iterate through the array to calculate base satisfaction (O(N)O(N)).
    • We perform a single pass with the sliding window, performing constant time operations per element (O(1)O(1) amortized) for each step. Total is linear relative to input size N.
  • Space Complexity: O(1)O(1)
    • We use only a few integer variables (base_satisfied, current_gain, max_gain) regardless of the input size. No auxiliary data structures like hash maps or extra arrays are required beyond the inputs themselves.

Solution

def maxSatisfied(customers, grumpy, X):
    n = len(customers)
    
    # 1. Calculate base satisfaction (customers satisfied naturally where owner is not grumpy)
    base_satisfaction = sum(c for c, g in zip(customers, grumpy) if g == 0)
    
    # 2. Initialize sliding window gain calculation
    # We only care about customers when the owner IS grumpy inside our technique window
    current_gain = sum(c for i, (c, g) in enumerate(zip(customers, grumpy)) 
                       if X > i and g == 1)
    
    max_gain = current_gain
    
    # 3. Slide the window across the array
    # We start sliding from index X to n-1
    for i in range(X, n):
        entering_customer_idx = i
        leaving_customer_idx = i - X
        
        c_entering = customers[entering_customer_idx]
        g_entering = grumpy[entering_customer_idx]
        
        c_leaving = customers[leaving_customer_idx]
        g_leaving = grumpy[leaving_customer_idx]
        
        # Update gain: add entering if they were originally unsatisfied (grumpy), 
        # remove leaving only if they contributed to the previous window's loss.
        if g_entering == 1:
            current_gain += c_entering
        
        if g_leaving == 1:
            current_gain -= c_leaving
            
        max_gain = max(max_gain, current_gain)
        
    return base_satisfaction + max_gain

# Example usage matching the problem description
if __name__ == "__main__":
    customers = [1,0,1,2,1,1,7,5]
    grumpy = [0,1,0,1,0,1,0,1]
    X = 3
    print(maxSatisfied(customers, grumpy, X)) # Output: 16

Edge Cases Handled

  • X equals array length: The loop range for sliding will effectively not execute or handle the single window correctly. current_gain is calculated initially covering all elements where grumpy[i] == 1. If this covers everything, it returns base (0) + total grumpy customers = correct result.
  • No Grumpy Minutes: The initial sum for gain will be 0. Since no minutes are unsatisfied naturally (base_satisfaction captures all), the loop updates current_gain to remain 0. Result is simply total customers, which is correct.
  • All Customers Unsatisfied (Grumpy): If every minute has grumpy[i] == 1, then base_satisfaction starts at 0. The sliding window will find the maximum sum of any contiguous subarray of length X within the customer array. This correctly identifies the best minutes to save using the technique.
  • X = 1: The logic holds; it simply checks every single minute individually for gain and adds max found to base satisfaction.