1052. Grumpy Bookstore Owner
Problem Description
In this problem, we have a bookstore owner who has their store open for n
minutes. During each of those minutes, customers enter the store. The number of customers entering the store at the beginning of the i
th minute is given by customers[i]
. After each minute, all customers for that particular minute leave.
The bookstore owner's mood fluctuates, and this affects customer satisfaction. The mood is captured by an array grumpy
. If grumpy[i]
is 1
, the owner is grumpy in the i
th minute; if 0
, they are not grumpy. When the owner is grumpy, customers leaving in that minute are not satisfied.
However, the owner knows a secret technique that allows them to be not grumpy for minutes
consecutive minutes, but they can use this secret technique only once in the day.
The task is to determine the maximum number of customers that can be satisfied throughout the day by smartly applying the secret technique to a certain time window during the day.
Intuition
The solution aims to identify the best time segment where using the secret technique will result in the maximum number of satisfied customers. We can always satisfy customers when the owner is not grumpy, so these customers are not our focus. Instead, we want to maximize the number of satisfied customers during the owner's grumpy periods.
To achieve this, we observe that the key is to apply the secret technique during the consecutively grumpy moments when the number of customers is highest. Here's how the solution approaches the problem:
-
We track the number of customers that could be satisfied if the owner were not grumpy at all by adding up the number of customers during grumpy minutes. This gives us the total potential satisfaction if the owner were not grumpy.
-
Then, we create a sliding window with the width equal to
minutes
ā the duration for which the secret technique can be applied. As we slide this window across the grumpy minutes, we calculate the number of dissatisfied customers in this window. -
We keep track of the maximum number of these potentially dissatisfied customers that can be turned into satisfied customers by applying the secret technique in the current sliding window.
-
We use a variable
t
to calculate the temporary sum of customers that are currently not satisfied due to the owner being grumpy within the window. Whenever we move the window forward by a minute, we deduct the customers at the start of the window (if the owner was grumpy at that minute) and add the customers at the new end of the window (if the owner is grumpy at the new end). -
We keep adjusting the best maximum number of satisfied customers found so far (
ans
) each time we slide the window one minute forward by subtracting the number of unsatisfied customers in the window from the total potential satisfaction.
In the end, we return the maximum number of customers that can be satisfied which will include the number of customers that were satisfied when the owner was not grumpy and the additional customers that were satisfied when using the secret technique during the grumpy periods.
Learn more about Sliding Window patterns.
Solution Approach
The solution approach utilizes a sliding window to find the optimal minutes
to apply the secret technique so as to maximize the satisfaction of customers. Here's how the implementation details map to this strategy:
-
We first calculate
s
, the sum of customers that are not satisfied initially due to the owner being grumpy. This is done by taking the dot product of thecustomers
andgrumpy
arrays. Only the minutes when the owner is grumpy (grumpy[i] == 1
) contribute tos
. -
cs
registers the total number of customers that visit the store throughout the day, which is the sum of the entirecustomers
array without taking the owner's mood into account. -
Two variables
t
andans
are initiated to zero.t
will capture the total number of dissatisfied customers within the current window, andans
will store the maximum number of customers that can be satisfied during the best window ofminutes
. -
We then iterate through each minute
i
, simultaneously calculating the sliding window sumt
for grumpy minutes. We do this by incrementingt
bycustomers[i]
only ifgrumpy[i] == 1
. -
In each iteration, we check if the sliding window has extended beyond the prescribed
minutes
. This is done using a condition(j := i - minutes) >= 0
. If true, it means we have a full window and we are moving it one step forward. -
We calculate the potential maximum number of satisfied customers
ans
by subtracting fromcs
the total dissatisfaction without the current window (s - t
). If it exceeds our previous best (ans
), we updateans
. -
After updating
ans
, we adjustt
by subtracting the customers at the starting point of the previous window frame, but only if that minute was a grumpy one (customers[j] * grumpy[j]
). -
Once the loop is done, all possible windows of size
minutes
have been checked. Theans
variable holds the maximum number of customers that can be satisfied by applying the secret technique during the best possible window. This value is returned.
Through the use of a simple loop and the sliding window technique, the implementation finds the optimal moment to use the secret technique without the need for complex data structures or algorithms. This is an efficient and effective solution for the given problem that runs in linear time, based on the number of minutes the store is open (O(n)
).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider the bookstore is open for n = 7
minutes, and the number of customers entering at each minute is given by customers = [1, 10, 10, 1, 1, 10, 10]
. The owner's mood over the 7 minutes is represented by grumpy = [0, 1, 1, 1, 0, 1, 0]
, and the owner can be not grumpy for minutes = 3
consecutive minutes using the secret technique.
-
We first calculate the total potential satisfaction without using the secret technique, which is the sum of customers that visit when the owner is not grumpy. From our example, this is
1 (1st minute) + 1 (5th minute) + 10 (7th minute) = 12
. -
Next, using a sliding window of size
minutes = 3
, we want to find a period where applying the secret technique can maximize customer satisfaction. We start with the window at the beginning:
- For the first window (
minutes 1-3
), the owner is in a good mood in the 1st minute, but grumpy in the 2nd and 3rd minute, where we have 10 + 10 customers, but we skip the 1st minute since the owner is not grumpy.
-
We slide the window to the right by one minute (
minutes 2-4
), the owner is grumpy in all these minutes, resulting in 10 + 10 + 1 customers. -
Continuing to slide our window to the right (
minutes 3-5
,minutes 4-6
), we find the maximum number of grumpy customers that would be satisfied by the secret technique. The windowminutes 4-6
is where the owner is constantly grumpy with customers[10, 1, 10]
. -
As we slide, we update the temporary sum
t
as we go, adding new customers who entered during a grumpy minute and subtracting those at the starting minute if it was a grumpy period. -
After sliding through all possible windows, the window
minutes 4-6
has the highest number of grumpy customers (1 + 10 + 10 = 21
) that could be turned into satisfied customers. -
The result is the sum of the initial satisfaction (12) and the additional satisfaction during the owner's grumpy period (21) when using the secret technique, which gives us the maximum customer satisfaction with the technique applied being 33.
-
Therefore, by applying the secret technique from the 4th to the 6th minute, the owner can maximize the number of satisfied customers for that day, resulting in a total satisfaction of 33 customers.
Solution Implementation
1class Solution:
2 def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
3 # Calculate the initial unsatisfied customer count (when the owner is grumpy)
4 unsatisfied = sum(customer * grumpiness for customer, grumpiness in zip(customers, grumpy))
5
6 # Calculate the total number of customers
7 total_customers = sum(customers)
8
9 # Tracking variable for the current window of grumpy period that can be improved
10 temp_improved = max_improved = 0
11
12 # Enumerate through each minute
13 for minute_index, (customer, grumpiness) in enumerate(zip(customers, grumpy), 1):
14 # Increase the count of potentially satisfied customers when the owner is grumpy
15 temp_improved += customer * grumpiness
16
17 # Slide the window of minutes for the "X" minute period
18 if (start_index := minute_index - minutes) >= 0:
19 # Update the max potential customers satisfied for any "X" minute window
20 max_improved = max(max_improved, total_customers - (unsatisfied - temp_improved))
21
22 # Remove the front of the window (the oldest minute moving out of the window)
23 temp_improved -= customers[start_index] * grumpy[start_index]
24
25 # The answer is the maximum potential customers satisfied in any "X" minute window
26 return max_improved
27
1class Solution {
2 public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
3 int totalGrumpyCustomers = 0; // This will hold the total number of customers affected by grumpiness
4 int totalCustomersSatisfied = 0; // Sum of all customers that are satisfied
5 int numCustomers = customers.length; // Total number of customers
6
7 // Calculate the initial total number of customers that are satisfied and the total affected by grumpiness
8 for (int i = 0; i < numCustomers; ++i) {
9 if (grumpy[i] == 1) {
10 // If the owner is grumpy during customer i's visit, add to totalGrumpyCustomers
11 totalGrumpyCustomers += customers[i];
12 }
13 // Add to the total number of satisfied customers regardless of grumpiness
14 totalCustomersSatisfied += customers[i];
15 }
16
17 int temporaryGrumpyCustomers = 0; // Temporary variable to keep track of grumpy customers during the 'minutes' window
18 int maxGrumpyCustomersConverted = 0; // Maximum number of grumpy customers that can be converted to satisfied customers
19 for (int i = 0; i < numCustomers; ++i) {
20 // If the owner is grumpy, temporarily add this customer to the count
21 if (grumpy[i] == 1) {
22 temporaryGrumpyCustomers += customers[i];
23 }
24 // If we are beyond the 'minutes' window, subtract the customers at the start of the window
25 if (i >= minutes) {
26 if (grumpy[i - minutes] == 1) {
27 temporaryGrumpyCustomers -= customers[i - minutes];
28 }
29 }
30
31 // Store the higher value between the current and previous maximum number of convertible grumpy customers
32 maxGrumpyCustomersConverted = Math.max(maxGrumpyCustomersConverted, temporaryGrumpyCustomers);
33 }
34
35 // Calculate final answer: Subtract the initial grumpy customers from the total customers satisfied and add the convertible grumpy customers
36 return totalCustomersSatisfied - totalGrumpyCustomers + maxGrumpyCustomersConverted;
37 }
38}
39
1class Solution {
2public:
3 int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
4 int totalUnsatisfied = 0; // To keep track of the total unsatisfied customers if the owner is grumpy
5 int totalCustomers = 0; // To keep track of the total number of customers served satisfactorily whether the owner is grumpy or not
6 int windowUnsatisfied = 0; // To keep track of unsatisfied customers in the current time window of size 'minutes'
7 int maxIncrease = 0; // Variable to store the maximum increase in satisfied customers achievable by using the technique for 'minutes' long
8
9 int n = customers.size(); // Total number of customers, assuming customers and grumpy are of same size
10 // Calculate the initial state, considering the owner is grumpy all the time
11 for (int i = 0; i < n; ++i) {
12 totalUnsatisfied += customers[i] * grumpy[i]; // Only add customers that are unsatisfied because the owner is grumpy
13 totalCustomers += customers[i]; // Add all customers
14 }
15
16 // Use a sliding window to determine when to utilize the owner's technique
17 for (int i = 0; i < n; ++i) {
18 windowUnsatisfied += customers[i] * grumpy[i]; // Add to window unsatisfied customers
19 int endTime = i - minutes; // Calculate end time of window (i - minutes + 1) - 1 for 0-based indexing
20
21 // If we've filled the first window, start calculating and updating maxIncrease
22 if (endTime >= 0) {
23 // Calculate the maximum satisfied customers by using the technique
24 maxIncrease = max(maxIncrease, totalCustomers - (totalUnsatisfied - windowUnsatisfied));
25 // Shrink the window from the left by removing the first element's impact if it was unsatisfied
26 windowUnsatisfied -= customers[endTime] * grumpy[endTime];
27 }
28 }
29 // After the loop, we must do one last check as the sliding window does not check the last window position
30 maxIncrease = max(maxIncrease, totalCustomers - (totalUnsatisfied - windowUnsatisfied));
31
32 // The answer is the maximum customers possible by using the technique in the best time window
33 return maxIncrease;
34 }
35};
36
1let totalUnsatisfied: number = 0; // Track total unsatisfied customers if the owner is grumpy
2let totalCustomers: number = 0; // Track total number of customers served satisfactorily
3let windowUnsatisfied: number = 0; // Track unsatisfied customers in the current 'minutes' window
4let maxIncrease: number = 0; // Maximum increase in satisfied customers possible by not being grumpy for 'minutes' duration
5
6function maxSatisfied(customers: number[], grumpy: number[], minutes: number): number {
7 totalUnsatisfied = 0;
8 totalCustomers = 0;
9 windowUnsatisfied = 0;
10 maxIncrease = 0;
11
12 const n: number = customers.length;
13 // Initial calculations without utilizing the special technique
14 for (let i = 0; i < n; i++) {
15 totalUnsatisfied += customers[i] * grumpy[i];
16 totalCustomers += customers[i];
17 }
18
19 // Using a sliding window to find the best time to apply the technique
20 for (let i = 0; i < n; i++) {
21 windowUnsatisfied += customers[i] * grumpy[i];
22 let endTime: number = i - minutes;
23
24 if (endTime >= 0) {
25 maxIncrease = Math.max(maxIncrease, totalCustomers - (totalUnsatisfied - windowUnsatisfied));
26 windowUnsatisfied -= customers[endTime] * grumpy[endTime];
27 }
28 }
29 // Handle the last possible window to make sure we don't miss the chance of optimizing at the end
30 maxIncrease = Math.max(maxIncrease, totalCustomers - (totalUnsatisfied - windowUnsatisfied));
31
32 // The result is the best scenario where the technique is applied in the optimal window
33 return maxIncrease;
34}
35
Time and Space Complexity
The time complexity of the provided code is O(N)
, where N
is the length of the customers
or grumpy
lists. This is because the code consists of a single loop that iterates over the entire length of the input lists exactly once. Within the loop, there are constant-time operations being performed, such as arithmetic operations, comparisons, and an assignment inside an if-statement that triggers based on the loop index.
The space complexity of the code is O(1)
, meaning it requires constant additional space. The extra space used in the algorithm is for variables s
, cs
, t
, ans
, and j
(the latter found in the conditional if-statement). These variables do not depend on the size of the input, hence the constant space complexity. No additional data structures or variable-sized containers are used that would require space proportional to the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which technique can we use to find the middle of a linked list?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!