Grumpy Bookstore Owner solution and explanation
IBM
9 more videos on this problem
Grumpy Bookstore Owner - Leetcode 1052 - PythonNeetCodeIO · 7:58 · 14K views
Grumpy Bookstore Owner | Simplest Thought Process | Leetcode 1052 | codestorywithMIKcodestorywithMIK · 29:24 · 14K views
1052. Grumpy Bookstore Owner | Sliding Window | Walmart Labs | EPAM SystemsAryan Mittal · 12:49 · 6K views
1052. Grumpy Bookstore Owner (Leetcode Medium)Programming Live with Larry · 24:00 · 2K views
✅ Grumpy Bookstore Owner - LeetCode 1052 - Sliding Window - Explained in Detail - Easy ApproachLeet Logics · 9:22 · 1K views
Leetcode 1052. Grumpy Bookstore OwnerFearless Learner · 4:27 · 619 views
1052. Grumpy Bookstore Owner || Java || Leetcode || HindiCoding Sphere · 11:26 · 583 views
Daily Leetcode #1543: Jun 21, 2024 - 1052. Grumpy Bookstore OwnerProgramming Live with Larry · 13:50 · 432 views
LeetCode 1052 | Grumpy Bookstore Owner | Array | Sliding Window | #leetcodedailychallenge #arraysAlgo Horizon · 11:26 · 180 views
LeetCode 1052 - Grumpy Bookstore Owner - JavaAlpha-Code · 15:15 · 138 views
The problem
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.length1 <= minutes <= n <= 2 * 1040 <= customers[i] <= 1000grumpy[i]is either0or1.
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.
def max_satisfied(customers, grumpy, minutes):
total_satisfaction = sum(c for c, g in zip(customers, grumpy) if not g)
max_extra_satisfaction = current_extra_satisfaction = 0
for i in range(len(customers)):
if grumpy[i]:
current_extra_satisfaction += customers[i]
if i >= minutes and grumpy[i - minutes]:
current_extra_satisfaction -= customers[i - minutes]
max_extra_satisfaction = max(max_extra_satisfaction, current_extra_satisfaction)
return total_satisfaction + max_extra_satisfaction
customers = [1, 0, 1, 2, 1, 1, 7, 5]
grumpy = [0, 1, 0, 1, 0, 1, 0, 1]
minutes = 3
result = max_satisfied(customers, grumpy, minutes)
print(f'Max satisfied customers: {result}')public class MaxSatisfied {
public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int totalSatisfaction = 0, maxExtraSatisfaction = 0, currentExtraSatisfaction = 0;
int n = customers.length;
for (int i = 0; i < n; ++i) {
if (grumpy[i] == 0) {
totalSatisfaction += customers[i];
}
}
for (int i = 0; i < n; ++i) {
if (grumpy[i] == 1) {
currentExtraSatisfaction += customers[i];
}
if (i >= minutes) {
if (grumpy[i - minutes] == 1) {
currentExtraSatisfaction -= customers[i - minutes];
}
}
maxExtraSatisfaction = Math.max(maxExtraSatisfaction, currentExtraSatisfaction);
}
return totalSatisfaction + maxExtraSatisfaction;
}
public static void main(String[] args) {
int[] customers = {1, 0, 1, 2, 1, 1, 7, 5};
int[] grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
int minutes = 3;
System.out.println("Max satisfied customers: " + maxSatisfied(customers, grumpy, minutes));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int total_satisfaction = 0, max_extra_satisfaction = 0, current_extra_satisfaction = 0;
int n = customers.size();
for (int i = 0; i < n; ++i) {
if (!grumpy[i])
total_satisfaction += customers[i];
}
for (int i = 0; i < n; ++i) {
if (grumpy[i]) {
current_extra_satisfaction += customers[i];
}
if (i >= minutes) {
if (grumpy[i - minutes])
current_extra_satisfaction -= customers[i - minutes];
}
max_extra_satisfaction = max(max_extra_satisfaction, current_extra_satisfaction);
}
return total_satisfaction + max_extra_satisfaction;
}
int main() {
vector<int> customers = {1, 0, 1, 2, 1, 1, 7, 5};
vector<int> grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
int minutes = 3;
cout << "Max satisfied customers: " << maxSatisfied(customers, grumpy, minutes) << endl;
return 0;
}function maxSatisfied(customers, grumpy, minutes) {
let totalSatisfaction = 0, maxExtraSatisfaction = 0, currentExtraSatisfaction = 0;
for (let i = 0; i < customers.length; i++) {
if (grumpy[i] === 0) {
totalSatisfaction += customers[i];
}
}
for (let i = 0; i < customers.length; i++) {
if (grumpy[i] === 1) {
currentExtraSatisfaction += customers[i];
}
if (i >= minutes && grumpy[i - minutes] === 1) {
currentExtraSatisfaction -= customers[i - minutes];
}
maxExtraSatisfaction = Math.max(maxExtraSatisfaction, currentExtraSatisfaction);
}
return totalSatisfaction + maxExtraSatisfaction;
}
const customers = [1, 0, 1, 2, 1, 1, 7, 5];
const grumpy = [0, 1, 0, 1, 0, 1, 0, 1];
const minutes = 3;
console.log(`Max satisfied customers: ${maxSatisfied(customers, grumpy, minutes)}`);#include <stdio.h>
int maxSatisfied(int* customers, int customersSize, int* grumpy, int grumpySize, int minutes){
int total_satisfaction = 0, max_extra_satisfaction = 0, current_extra_satisfaction = 0;
// Calculate initial satisfaction for non-grumpy minutes
for (int i = 0; i < customersSize; ++i) {
if (!grumpy[i])
total_satisfaction += customers[i];
}
// Use sliding window to find max additional satisfaction in grumpy period
for (int i = 0; i < customersSize; ++i) {
if (grumpy[i]) {
current_extra_satisfaction += customers[i];
}
if (i >= minutes) {
if (grumpy[i - minutes])
current_extra_satisfaction -= customers[i - minutes];
}
if (current_extra_satisfaction > max_extra_satisfaction)
max_extra_satisfaction = current_extra_satisfaction;
}
return total_satisfaction + max_extra_satisfaction;
}
int main() {
int customers[] = {1, 0, 1, 2, 1, 1, 7, 5};
int grumpy[] = {0, 1, 0, 1, 0, 1, 0, 1};
int minutes = 3;
int result = maxSatisfied(customers, 8, grumpy, 8, minutes);
printf("Max satisfied customers: %d\n", result);
return 0;
}using System;
public class MaxSatisfied {
public static int MaxSatisfiedCustomers(int[] customers, int[] grumpy, int minutes) {
int totalSatisfaction = 0, maxExtraSatisfaction = 0, currentExtraSatisfaction = 0;
int n = customers.Length;
for (int i = 0; i < n; ++i) {
if (grumpy[i] == 0) {
totalSatisfaction += customers[i];
}
}
for (int i = 0; i < n; ++i) {
if (grumpy[i] == 1) {
currentExtraSatisfaction += customers[i];
}
if (i >= minutes) {
if (grumpy[i - minutes] == 1) {
currentExtraSatisfaction -= customers[i - minutes];
}
}
maxExtraSatisfaction = Math.Max(maxExtraSatisfaction, currentExtraSatisfaction);
}
return totalSatisfaction + maxExtraSatisfaction;
}
public static void Main() {
int[] customers = {1, 0, 1, 2, 1, 1, 7, 5};
int[] grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
int minutes = 3;
Console.WriteLine("Max satisfied customers: " + MaxSatisfiedCustomers(customers, grumpy, minutes));
}
}In this Python solution, the key insight is to split the problem into two parts: calculate base satisfaction for non-grumpy periods and find the maximum possible additional satisfaction using a sliding window over the grumpy periods. The approach pursues an O(n) time complexity by efficiently leveraging the zip function and sliding window technique.
Time Complexity: O(n)
Space Complexity: O(1)
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).
function maxSatisfied(customers: number[], grumpy: number[], minutes: number): number {
let [cnt, tot] = [0, 0];
for (let i = 0; i < minutes; ++i) {
cnt += customers[i] * grumpy[i];
tot += customers[i] * (grumpy[i] ^ 1);
}
let mx = cnt;
for (let i = minutes; i < customers.length; ++i) {
cnt += customers[i] * grumpy[i];
cnt -= customers[i - minutes] * grumpy[i - minutes];
mx = Math.max(mx, cnt);
tot += customers[i] * (grumpy[i] ^ 1);
}
return tot + mx;
}func maxSatisfied(customers []int, grumpy []int, minutes int) int {
var cnt, tot int
for i, c := range customers[:minutes] {
cnt += c * grumpy[i]
tot += c * (grumpy[i] ^ 1)
}
mx := cnt
for i := minutes; i < len(customers); i++ {
cnt += customers[i] * grumpy[i]
cnt -= customers[i-minutes] * grumpy[i-minutes]
mx = max(mx, cnt)
tot += customers[i] * (grumpy[i] ^ 1)
}
return tot + mx
}impl Solution {
pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 {
let mut cnt = 0;
let mut tot = 0;
let minutes = minutes as usize;
for i in 0..minutes {
cnt += customers[i] * grumpy[i];
tot += customers[i] * (1 - grumpy[i]);
}
let mut mx = cnt;
let n = customers.len();
for i in minutes..n {
cnt += customers[i] * grumpy[i];
cnt -= customers[i - minutes] * grumpy[i - minutes];
mx = mx.max(cnt);
tot += customers[i] * (1 - grumpy[i]);
}
tot + mx
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window for Extra Satisfaction | Time Complexity: O(n) Space Complexity: O(1) |
| Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Window Check | O(n * X) | O(1) | When first reasoning about the problem or when constraints are very small |
| Sliding Window for Extra Satisfaction | O(n) | O(1) | Optimal solution for large arrays; interview-preferred approach |
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.