Grumpy Bookstore Owner Solution In C++/Java/Python/JS
Problem Description:
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 ,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.
Examples:
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 from getting grumpy for the last 3 minutes. The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
Input: customers = [1], grumpy = [0], minutes = 1
Output: 1
Explanation:
Only 1 customer enters the bookstore in the first minute, and also at that time owner is not grumpy, hence, output is 1.
Constraints:
- n == customers.length == grumpy.length
- 1 <= minutes <= n <= 2 * 104
- 0 <= customers[i] <= 1000
- grumpy[i] is either 0 or 1.
Brute Force Approach
Let’s break down this problem together! We’re given two arrays: one called customers and another called grumpy.
For every minute I:
- customers[i] tells us how many customers walk into the store,
- grumpy[i] reveals if the owner is grumpy at that moment. 1 means yes, and 0 means no.
Here’s an interesting twist: The owner has a special power. For "minutes" consecutive, he can force himself to be cheerful instead of grumpy. Let’s use k as our variable for how long the owner can hold onto their good mood.
So, our task? Figure out the maximum number of customers who can be happily attended by the owner, thanks to this cheering-up window.
Let’s think about how we can do this:
Some critical observations:
If the owner’s mood is good at a particular minute (grumpy[i] == 0), he’ll attend to all the customers at that minute, no problem! These customers should always be counted.
For every other moment, when the owner is grumpy (grumpy[i] == 1), those customers might only get cheerful service if their visit happens to fall within the owner’s special “not grumpy” interval of length k.
Intuition:
From the first observation, we can start by totalling all customers the owner naturally serves happily (when grumpy[i] = 0). Not much work here.
We know the store owner has an interesting power: for k consecutive minutes, he can suppress his grumpiness, no matter what. This means, within any chosen block of k minutes, even if he’d normally be grumpy, he can ensure all those customers get his full attention.
How to check for a k-minute block to add more customers?
Let's think through what this unlocks. For every possible starting minute from 0 up to n-k (where n is the total number of minutes), we can imagine activating this "good mood" power.
For each starting point, we focus on the k-minute stretch that follows. Within this period, we look specifically for all those minutes where the owner was originally grumpy; these are the moments where customer satisfaction would have been lost. By covering these minutes with the owner’s temporary power, we can "save" those customers for the total count.
What makes this approach effective is that we repeat this exploration for every eligible starting minute, keeping track of which stretch helps the most grumpy-affected customers.
Your final answer?
Add the always-happy customers from step 1 to the best “cheering up” result from step 2.
And that’s it, logical, and easy to follow! Just pay attention to when the owner is naturally in a good mood and find the stretch of k minutes that make our answer better
Grumpy Bookstore Owner Example
Input: customers = [1, 2, 3, 4, 5], grumpy = [1, 0, 1, 0, 1]], minutes = 2
Output: 11
Explanation: The 2 and 4 already add to answer because owner is not grumpy then we can use owners special power on last k consecutive indices adding additional 5 to the answer giving total of 11.
Count already satisfied customers
We iterate through the grumpy array and add customers[i] to the total ans only when grumpy[i] == 0.
- At index 0: grumpy → 1 → not added
- At index 1: grumpy → 0 → add customers[1] = 2
- At index 2: grumpy → 1 → not added
- At index 3: grumpy → 0 → add customers[3] = 4
- At index 4: grumpy → 1 → not added
So: ans = 2 + 4 = 6
Try every starting point and take the size of minutes = 2 and compute the max recoverable grumpy customers
We try each valid starting index i from 0 to n - minutes (i.e., 0 to 3), and check how many customers could be recovered if we apply the technique during that window.
➤ Starting from index 0 to 1:
- grumpy[0] = 1 → add customers[0] = 1
- grumpy[1] = 0 → skip
→ Total recoverable: 1
→ extra = max(0, 1) = 1
➤ Starting from index 1 to 2:
- grumpy[1] = 0 → skip
- grumpy[2] = 1 → add customers[2] = 3
→ Total recoverable: 3
→ extra = max(1, 3) = 3
➤ Starting from index 2 to 3:
- grumpy[2] = 1 → add customers[2] = 3
- grumpy[3] = 0 → skip
→ Total recoverable: 3
→ extra = max(3, 3) = 3
➤ Starting from index 3 to 4:
- grumpy[3] = 0 → skip
- grumpy[4] = 1 → add customers[4] = 5
→ Total recoverable: 5
→ extra = max(3, 5) = 5
Final Step:
Base satisfied = ans = 6
Best additional (extra) satisfied = extra = 5
return ans + extra; (6 + 5 = 11)
Grumpy Bookstore Owner Solution
Step 1: Initialize variables
- Determine the number of minutes (n) using grumpy.size().
- Initialize ans = 0 to keep track of customers who are already satisfied (i.e., when the owner is not grumpy).
Step 2: Traverse the grumpy array once
- For each index i from 0 to n-1, check:
- If grumpy[i] == 0, then the owner was not grumpy.
- Add customers[i] to ans since those customers are already satisfied.
Step 3: Set up variables for tracking extra customers
- Initialize:
- extra = 0: This will hold the maximum number of additional customers we can satisfy by using the technique.
- curr = 0: This will be used inside a loop to calculate the current window’s extra satisfied customers.
Step 4: Use a nested loop to try every possible window
- Outer loop: Go from i = 0 to i <= n - minutes
- This means we're trying every starting index i of the window.
- Inner loop: Go from j = i to j < i + minutes
- For each index j, check if grumpy[j] == 1.
- If so, the customer at j would normally be unsatisfied, but if we apply the technique here, they will be satisfied.
- Add customers[j] to curr.
Step 5: Track the best window
- After each inner loop finishes, compare curr with extra:
- extra = max(extra, curr)
- This ensures you're always tracking the window that would recover the most customers.
Step 6: Final result
- After all windows are checked, add the extra recovered customers to the ans already satisfied.
Grumpy Bookstore Owner leetcode solution
Grumpy Bookstore Owner solution in C++
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int n = grumpy.size();
int ans = 0;
// Count customers already satisfied (grumpy[i] == 0)
for (int i = 0; i < n; ++i) {
if (grumpy[i] == 0) ans += customers[i];
}
int extra = 0;
// Brute-force window of size `minutes`
for (int i = 0; i <= n - minutes; ++i) {
int curr = 0;
for (int j = i; j < i + minutes; ++j) {
if (grumpy[j] == 1) {
curr += customers[j];
}
}
extra = max(extra, curr);
}
return ans + extra;
}
};Grumpy Bookstore Owner solution in java
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int n = grumpy.length;
int ans = 0;
// Count customers already satisfied
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) ans += customers[i];
}
int extra = 0;
// Brute-force each window of size `minutes`
for (int i = 0; i <= n - minutes; i++) {
int curr = 0;
for (int j = i; j < i + minutes; j++) {
if (grumpy[j] == 1) {
curr += customers[j];
}
}
extra = Math.max(extra, curr);
}
return ans + extra;
}
}Grumpy Bookstore Owner solution in Python
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
n = len(grumpy)
ans = 0
# Count customers already satisfied (grumpy[i] == 0)
for i in range(n):
if grumpy[i] == 0:
ans += customers[i]
extra = 0
# Brute-force each window of size `minutes`
for i in range(n - minutes + 1):
curr = 0
for j in range(i, i + minutes):
if grumpy[j] == 1:
curr += customers[j]
extra = max(extra, curr)
return ans + extraGrumpy Bookstore Owner solution in Javascript
/**
* @param {number[]} customers
* @param {number[]} grumpy
* @param {number} minutes
* @return {number}
*/
var maxSatisfied = function(customers, grumpy, minutes) {
const n = grumpy.length;
let ans = 0;
// Count customers already satisfied
for (let i = 0; i < n; i++) {
if (grumpy[i] === 0) ans += customers[i];
}
let extra = 0;
// Brute-force each window of size `minutes`
for (let i = 0; i <= n - minutes; i++) {
let curr = 0;
for (let j = i; j < i + minutes; j++) {
if (grumpy[j] === 1) {
curr += customers[j];
}
}
extra = Math.max(extra, curr);
}
return ans + extra;
};Grumpy Bookstore Owner Complexity Analysis
Time Complexity: O(n × k)
Step-by-Step Complexity Breakdown
Let:
- n = total number of minutes (customers.size() or grumpy.size())
- k = minutes (duration for which we can suppress grumpiness)
1. Outer loop:
Runs from i = 0 to i <= n - k
- Number of iterations:
→ (n - k + 1) ≈ O(n) in the worst case
2. Inner loop:
For every i, loop runs from j = i to j < i + k
- That is, exactly k iterations for each i
- Each inner loop does:
- A check if (grumpy[j] == 1)
- A conditional addition curr += customers[j]
- So each inner loop costs O(k) time
Total Time Complexity:
Since the outer loop runs ≈ O(n) times, and for each, the inner loop runs O(k) times:
O(n) × O(k) = O(n × k)
Where:
- n is the length of the input
- k is the minutes value
Space Complexity: O(n)
- Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm itself, excluding input and output.
- Variables used:
- int ans, curr, extra, i, j → all are scalar integers
- No additional data structures (arrays, hash maps, etc.) are used
Auxiliary Space complexity: O(1)
- Total Space Complexity
Total space complexity = Auxiliary space + Input space + Output space
- Input:
- vector<int>& customers → size n
- vector<int>& grumpy → size n
- Output:
- A single integer (the final result)
Input space: O(n)
utput space: O(1)
Total Space Complexity: O(n)
Is the brute force approach efficient?
The time complexity of the brute-force approach is O(n × k), where for each starting point i, we loop from i to i + k to account for k consecutive customers.
In our case, n ≤ 1000 and k ≤ 2 × 10⁴, so in the worst case we perform up to 2 × 10⁷ operations. This is within acceptable limits and the solution will pass, but it comes with a high running time, especially on larger inputs.
To improve this, we can build an optimized approach by combining the intuition from the brute-force method.
Optimal Approach
Our brute-force solution is divided into two parts:
First, we initially count the customers entering during each minute i where grumpy[i] is 0, because those customers are always satisfied regardless of any technique we apply.
Then, we traverse through every possible starting point from i = 0 to n-k and for each of these, we check for k consecutive customers from i to i+k-1. For every such segment, we calculate how many of those customers are associated with grumpy[i] == 1, because that’s the number we can potentially convert into satisfied customers by applying the secret power.
Now, if we look at the observation, it becomes clear that our main goal is to focus on a window of exactly k consecutive minutes.
To put it more formally, we are trying to find a subarray of size k in the customers array such that within that subarray, the sum of customers where grumpy[i] == 1 is maximum. These are the only customers that would change from unsatisfied to satisfied if we apply the technique during those k minutes.
What are we doing new?
In the brute-force version, we went to every starting point and calculated the sum from i to i + k - 1 again and again. But if we observe carefully, this is inefficient and redundant. Starting from i = 0, we compute the first k-minute window: 0 to k-1. Now, instead of recalculating everything from scratch for i = 1, we can reuse part of the previous result. For the next window 1 to k, we just:
- Remove the effect of the first element (at index i - 1)
- Add the effect of the new element entering the window (at index i + k)
So the windows move like this:
- 0 to k-1
- 1 to k
- 2 to k+1
- 3 to k+2
… and so on. Every time, it’s just about sliding the window by one unit to the right.
To implement this efficiently, we can use two pointers, the low and high, and maintain a variable curr to keep track of the current sum of customers within the window where the grumpy value is 1. We also maintain a variable extra to store the maximum sum we've encountered so far, which represents the best window to apply the secret technique.
As we slide the window:
- We increase high by 1 to grow the window, and if grumpy[high] == 1, we add customers[high] to curr.
- If the window size exceeds k, we shrink it by:
- Removing customers[low] from curr only if grumpy[low] == 1
- Increasing the low to maintain the window size
By maintaining this window in a sliding manner, we avoid repeated calculations and achieve a much faster, efficient solution.
Animation of Grumpy Bookstore Owner - Optimal Solution
Grumpy Bookstore Owner Example
Input: customers = [1, 2, 3, 4, 5], grumpy = [1, 0, 1, 0, 1]], minutes = 2
Output: 11
Explanation: The 2 and 4 already add to answer because owner is not grumpy then we can use owners special power on last k consecutive indices adding additional 5 to the answer giving total of 11.
Count always-satisfied customers
We iterate over all i from 0 to n - 1, and add customers[i] to ans only if grumpy[i] == 0.
- grumpy[0] = 1 → skip
- grumpy[1] = 0 → add customers[1] = 2
- grumpy[2] = 1 → skip
- grumpy[3] = 0 → add customers[3] = 4
- grumpy[4] = 1 → skip
Result: ans = 2 + 4 = 6
This is the base number of customers satisfied even without using the technique.
Use a sliding window to find max extra recoverable customers
We maintain a window of size at most minutes = 2.
We initialize: extra = 0, curr = 0, low = 0, high = 0
➤ Iteration 1: high = 0
- grumpy[0] = 1 → add customers[0] = 1 → curr = 1
- Window size: high - low + 1 = 1 → valid
- Update extra: max(0, 1) = 1
- high++
➤ Iteration 2: high = 1
- grumpy[1] = 0 → skip
- Window size: 2 → valid
- Update extra: max(1, 1) = 1
- high++
➤ Iteration 3: high = 2
- grumpy[2] = 1 → add customers[2] = 3 → curr = 4
- Window size: high - low + 1 = 3 → exceeds minutes
- Check grumpy[low] = grumpy[0] = 1 → subtract customers[0] = 1 → curr = 3
- low++ → low = 1
- Update extra: max(1, 3) = 3
- high++
➤ Iteration 4: high = 3
- grumpy[3] = 0 → skip
- Window size: high - low + 1 = 3 → exceeds minutes
- grumpy[1] = 0 → no change to curr
- low++ → low = 2
- Update extra: max(3, 3) = 3
- high++
➤ Iteration 5: high = 4
- grumpy[4] = 1 → add customers[4] = 5 → curr = 8
- Window size = 3 → too big
- grumpy[2] = 1 → subtract customers[2] = 3 → curr = 5
- low++ → low = 3
- Update extra: max(3, 5) = 5
- high++
Final Calculation:
Base satisfied = ans = 6
Best additional (extra) satisfied = extra = 5
return ans + extra; (6 + 5 = 11)
Grumpy Bookstore Owner Algorithm
Step 1: Initialize variables
- Get the size of the input arrays in n
- Initialize a variable ans = 0 to store the number of customers already satisfied without any technique applied (i.e., during minutes when the owner is not grumpy).
Step 2: Traverse the arrays to count always-satisfied customers
- Loop through the array from i = 0 to n - 1
- If grumpy[i] == 0, the owner is not grumpy, so add customers[i] to ans
- These customers are always satisfied and do not depend on the special technique
Step 3: Initialize variables for the sliding window logic
- extra = 0: Stores the maximum number of additional customers we can satisfy by applying the technique during some window
- curr = 0: Tracks the current number of grumpy customers within the active window
- low = 0, high = 0: Two pointers representing the sliding window
Step 4: Start the sliding window traversal
Use a while (high < n) loop:
- If grumpy[high] == 1, include customers[high] in curr, since these customers are only recovered when the technique is applied
Step 5: Shrink the window when it exceeds the allowed time
- If the window size exceeds minutes, then move the low pointer forward to shrink it
- While shrinking:
- If grumpy[low] == 1, subtract customers[low] from curr since we're removing that grumpy customer from the window
- Then increment low to maintain window size
Step 6: Update the best result
- After adjusting the window, update extra with the maximum of current value and curr.
- Then, increment high to expand the window
Step 7: Final result
- After the sliding window has been processed, return the total number of satisfied customers:
Grumpy Bookstore Owner leetcode solution
Grumpy Bookstore Owner solution in C++
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int n = grumpy.size();
int ans = 0;
// Count customers already satisfied (when owner is not grumpy)
for (int i = 0; i < n; ++i) {
if (grumpy[i] == 0) ans += customers[i];
}
int extra = 0; // Maximum number of customers we can recover
int curr = 0; // Current window sum
int low = 0, high = 0;
// Sliding window to track max gain over `minutes` duration
while (high < n) {
// Add only grumpy customers to current window
if (grumpy[high] == 1) curr += customers[high];
// Maintain window size
if (high >= low + minutes) {
if (grumpy[low] == 1) curr -= customers[low];
low++;
}
extra = max(extra, curr); // Track maximum extra gain
high++;
}
return ans + extra; // Total satisfied = base + extra by technique
}
};Grumpy Bookstore Owner solution in java
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int n = grumpy.length;
int ans = 0;
// Count customers already satisfied without technique
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) ans += customers[i];
}
int curr = 0; // Current window value
int extra = 0; // Max additional satisfied customers
int low = 0, high = 0;
// Sliding window
while (high < n) {
if (grumpy[high] == 1) curr += customers[high];
// If window exceeds `minutes`, shrink from left
if (high >= low + minutes) {
if (grumpy[low] == 1) curr -= customers[low];
low++;
}
extra = Math.max(extra, curr);
high++;
}
return ans + extra;
}
}Grumpy Bookstore Owner solution in Python
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
n = len(grumpy)
ans = 0
# Count already satisfied customers
for i in range(n):
if grumpy[i] == 0:
ans += customers[i]
curr = 0 # Current window sum
extra = 0 # Maximum extra customers we can satisfy
low = 0
high = 0
# Sliding window technique
while high < n:
if grumpy[high] == 1:
curr += customers[high]
if high >= low + minutes:
if grumpy[low] == 1:
curr -= customers[low]
low += 1
extra = max(extra, curr)
high += 1
return ans + extraGrumpy Bookstore Owner solution in JavaScript
/**
* @param {number[]} customers
* @param {number[]} grumpy
* @param {number} minutes
* @return {number}
*/
var maxSatisfied = function(customers, grumpy, minutes) {
const n = grumpy.length;
let ans = 0;
// Count customers already satisfied
for (let i = 0; i < n; i++) {
if (grumpy[i] === 0) ans += customers[i];
}
let curr = 0; // Current window value
let extra = 0; // Max gain using technique
let low = 0, high = 0;
// Sliding window to track max recoverable customers
while (high < n) {
if (grumpy[high] === 1) curr += customers[high];
if (high >= low + minutes) {
if (grumpy[low] === 1) curr -= customers[low];
low++;
}
extra = Math.max(extra, curr);
high++;
}
return ans + extra;
}Grumpy Bookstore Owner Complexity Analysis
Time Complexity: O(n)
Step-by-Step Time Complexity Breakdown
Let:
- n = total number of elements in customers and grumpy
- minutes = size of the window (k)
Observations:
- We're using two pointers: low and high
- high moves from 0 to n - 1 → exactly n steps
- For each step, we do:
- 1 conditional check
- At most 1 addition/subtraction
- A max() operation
No nested loops, and every element is processed a constant number of times.
Hence the complexity: O(n).
Key Insight:
- Each element is added once when entering the window (high++)
- Each element is removed once when exiting the window (low++)
- All operations are O(1) per element
Final Time Complexity: O(n)
Space Complexity: O(n)
1. Auxiliary Space Complexity
Auxiliary space refers to additional memory used by the algorithm itself, excluding input and output.
- Variables used:
- Integers like n, ans, curr, extra, low, high → all are scalar variables
- No hash maps, arrays, or dynamic memory allocations are used
Auxiliary Space: O(1)
2. Total Space Complexity
Total space includes: Auxiliary space + Input space + Output space
Input:
- vector<int>& customers → size n
- vector<int>& grumpy → size n
Output:
- A single integer (the return value)
Input space: O(n)
Output space: O(1)
Total Space Complexity: O(n)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and `'u'.
You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:
- The length of the subarray is k, and
- All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.
A subarray is a contiguous non-empty sequence of elements within an array.