Similar Problems
Similar Problems not available
Grumpy Bookstore Owner  Leetcode Solution
Companies:
LeetCode: Grumpy Bookstore Owner Leetcode Solution
Difficulty: Medium
Topics: slidingwindow array
Here is a detailed solution for the Grumpy Bookstore Owner problem on LeetCode:
Problem Statement:
A bookstore owner has a store open for customers for N minutes. Every minute, some number of customers (customers[i]) come into the store, and all those customers leave after the end of that minute.
On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the ith minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise, they are satisfied.
The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Example:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation:
The bookstore owner keeps themselves not grumpy for the last 3 minutes, they can make the customers satisfied during the last 3 minutes.
So 1 + 0 + 1 + 2 + 1 + 1 + 7 + 5 = 18, but the bookstore owner only counts the satisfied customers in the last 3 minutes.
Therefore, the answer is 1 + 0 + 1 + 2 + 1 + 1 + 7 + 5 = 18.
Approach:
First, calculate the total number of satisfied customers without using the secret technique.
Then, Keep iterating through the customer array with the help of a sliding window. For each window, calculate the number of satisfied customers that can be gained by using the secret technique.
Return the sum of (total satisfied customers + satisfied customers gained by using the secret technique in a window of X minutes).
Steps:

Initialize the variables, such as a variable for total satisfied customers, satisfied customers without using the secret technique, and satisfied customers gained by using the secret technique.

Loop through the length of customers array.

Calculate the total satisfied customers by adding the number of satisfied customers at each minute.

Loop through the array again for the sliding window calculation.

Set left and right pointers for each window and track the sum of satisfied customers in the window.

Move the window one step at a time by moving the left pointer one step at a time and simultaneously deleting the customers that are no longer in the window and adjusting the window sum.

If we find a window of X minutes where the bookstore owner is grumpy, we calculate the number of satisfied customers that can be gained by using the secret technique and add it to the satisfied customers gained by using the secret technique variable.

Update the satisfied customers without using the secret technique variable to reflect the new satisfied customers after using the secret technique.

Return the sum of satisfied customers with and without using the secret technique.
Pseudo Code:
total_satisfied_customers = 0 satisfied_customers_without_technique = 0 satisfied_customers_with_technique = 0
Calculate the total customers satisfaction
for i in range(len(customers)): if grumpy[i] == 0: total_satisfied_customers += customers[i] satisfied_customers_without_technique += customers[i]
Search for the maximum customers satisfaction with help of secret technique
for i in range(X): if grumpy[i] == 1: satisfied_customers_with_technique += customers[i]
Sliding widnow technique
left = 0 for right in range(X, len(customers)): if grumpy[right] == 1: satisfied_customers_with_technique += customers[right] if grumpy[left] == 1: satisfied_customers_with_technique = customers[left] left += 1 satisfied_customers_without_technique += customers[right]  customers[left  1] return satisfied_customers_with_technique + satisfied_customers_without_technique
Time Complexity: The time complexity of the above algorithm is O(n), where n is the length of the input array. The algorithm involves just one loop to calculate total satisfied customers, another loop to calculate satisfied customers with secret technique and a sliding window approach of one iteration to get maximum customers satisfaction in X minutes.
Space Complexity: The algorithm uses only a constant amount of extra space, hence the space complexity is O(1).
Grumpy Bookstore Owner Solution Code
1