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 either 0 or 1.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.
C++
Java
Python
C#
JavaScript
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.
Grumpy Bookstore Owner - Leetcode 1052 - Python • NeetCodeIO • 11,264 views views
Watch 9 more video solutions →Practice Grumpy Bookstore Owner with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor