Skip to main content
Talentd

Grumpy Bookstore Owner - Solution & Explanation

MediumArraySliding Window15 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

There is a bookstore owner that has a store open for n minutes. You are given an integer array customers of length n where customers[i] is the number of the customers that enter the store at the start of the ith minute and all those customers leave after the end of that minute.

During certain minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.

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

The bookstore owner knows a secret technique to remain not grumpy for minutes consecutive minutes, but this technique can only be used once.

Return the maximum number of customers that can be satisfied throughout the day.

 

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

Explanation:

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

 

Constraints:

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

Approach Overview

Problem Overview: You run a bookstore where the owner is sometimes grumpy. When grumpy, customers during that minute leave unsatisfied. A secret technique can suppress grumpiness for X consecutive minutes. The goal is to choose the best window of X minutes that maximizes the total number of satisfied customers.

Approach 1: Brute Force Window Check (O(n * X) time, O(1) space)

Start by counting customers that are already satisfied when the owner is not grumpy. Then try every possible window of length X. For each window, iterate through its elements and add the customers that would become satisfied if grumpiness were suppressed there. Track the maximum extra satisfaction across all windows. This approach is straightforward but inefficient because each candidate window requires scanning up to X elements, producing O(n * X) time complexity.

Approach 2: Sliding Window for Extra Satisfaction (O(n) time, O(1) space)

The key insight: only customers during grumpy minutes matter for the special technique. First compute the baseline satisfaction by iterating once and summing customers where grumpy[i] == 0. Next, treat the extra customers gained from suppressing grumpiness as a sliding window problem. While scanning the array, add customers[i] to the window if grumpy[i] == 1. When the window size exceeds X, remove the contribution at i - X. Track the maximum extra gain seen in any window.

This converts repeated window recomputation into incremental updates. Each element enters and leaves the window once, so the total work is linear. The algorithm relies on sequential iteration and constant updates, a common pattern in sliding window problems. Since the data is stored in simple arrays, the logic also fits naturally within typical array traversal patterns.

After scanning the entire array, add the maximum extra satisfaction from the window to the baseline satisfied customers. The result represents the optimal placement of the grumpiness suppression technique.

Recommended for interviews: Interviewers expect the sliding window solution. The brute force method shows you understand the objective—testing every possible window—but the O(n) sliding window demonstrates stronger algorithmic thinking and the ability to optimize repeated computations. This pattern appears frequently in array optimization problems where a fixed-length segment must be chosen to maximize or minimize a value.

Approach 1: Sliding Window for Extra Satisfaction

This approach uses the sliding window technique to maximize the number of satisfied customers by calculating the additional satisfaction obtained by using the non-grumpy technique for a given number of consecutive minutes.

This solution calculates the initial base satisfaction for all non-grumpy minutes. It then uses a sliding window to determine the maximum additional satisfaction from applying the no-grumpy technique over any possible time frame. The approach efficiently ensures a time complexity of O(n), only making a single linear traversal of the input.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as it involves a single pass through the arrays.

Space Complexity: O(1), as no extra space beyond a few variables is used.

Try this approach in the editor →

Approach 2: 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.

We define a variable cnt to record the number of customers when the boss is angry within the sliding window, the initial value is the number of customers when the boss is angry in the first minutes. Then we traverse the array, each time we move the sliding window, we update the value of cnt, and at the same time update the value of mx.

Finally, return tot + mx.

The time complexity is O(n), where n is the length of the array customers. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window for Extra Satisfaction

Time Complexity: O(n), as it involves a single pass through the arrays.

Space Complexity: O(1), as no extra space beyond a few variables is used.

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window CheckO(n * X)O(1)When first reasoning about the problem or when constraints are very small
Sliding Window for Extra SatisfactionO(n)O(1)Optimal solution for large arrays; interview-preferred approach

Video Solution

Grumpy Bookstore Owner - Leetcode 1052 - Python • NeetCodeIO • 14,232 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Grumpy Bookstore Owner easy or hard?
Grumpy Bookstore Owner is rated Medium difficulty on LeetCode. The challenge lies in recognizing that only grumpy minutes matter for optimization and converting repeated window checks into an efficient sliding window with O(n) complexity.
How to solve Grumpy Bookstore Owner in O(n)?
Compute the baseline satisfied customers where grumpy[i] equals 0. Then use a sliding window of length X to track additional customers gained during grumpy minutes. Add customers when entering the window and subtract them when leaving it. Keep the maximum extra gain and add it to the baseline.
What is the best approach for Grumpy Bookstore Owner?
The sliding window approach is the optimal solution. First count customers already satisfied when the owner is not grumpy. Then use a window of size X to track the additional customers that could become satisfied if the technique suppresses grumpiness in that interval. This runs in O(n) time and O(1) space.
What data structure is used in Grumpy Bookstore Owner?
The problem mainly uses arrays and a sliding window technique. No advanced data structures are required. The algorithm maintains running sums while iterating through the arrays, updating values as elements enter and leave the window.
What is the time complexity of Grumpy Bookstore Owner?
The optimal algorithm runs in O(n) time because each element is processed once while maintaining a sliding window of size X. Space complexity is O(1) since only a few counters are maintained. A naive brute force approach would take O(n * X) time.
Grumpy Bookstore Owner Python or Java solution approach?
Both Python and Java implementations follow the same logic: compute baseline satisfaction, maintain a sliding window of size X for additional gain, and track the maximum window sum. The code typically uses a single pass through the arrays with constant extra variables.
Is Grumpy Bookstore Owner asked at Google, Amazon, or Meta?
Variants of sliding window optimization problems frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests array traversal, window management, and recognizing when a fixed-length sliding window can replace repeated subarray calculations.

Ready to solve this problem?

Practice Grumpy Bookstore Owner with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays