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.

Description Hints 1 Solution Video 7:58

1052. Grumpy Bookstore Owner

Medium64.2% acceptance7 companies

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 i^th 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 i^th 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 * 10⁴
0 <= customers[i] <= 1000
grumpy[i] is either 0 or 1.

Asked at 7 companies

Nutanix Capital One

IBM Amazon Microsoft Meta Bloomberg

Topics

Array Sliding Window

Hints open one at a time

Hint 1

Say the store owner uses their power in minute 1 to X and we have some answer A. If they instead use their power from minute 2 to X+1, we only have to use data from minutes 1, 2, X and X+1 to update our answer A.

7:58

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,0,1,2,1,1,7,5]
[0,1,0,1,0,1,0,1]
3

Input

[1]
[0]
1

Your code is saved on this device.Solution