1052. Grumpy Bookstore Owner

MediumArraySliding Window
Leetcode Link

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 ith 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 ith 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:

  1. 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.

  2. 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.

  3. 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.

  4. 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).

  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

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:

  1. 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 the customers and grumpy arrays. Only the minutes when the owner is grumpy (grumpy[i] == 1) contribute to s.

  2. cs registers the total number of customers that visit the store throughout the day, which is the sum of the entire customers array without taking the owner's mood into account.

  3. Two variables t and ans are initiated to zero. t will capture the total number of dissatisfied customers within the current window, and ans will store the maximum number of customers that can be satisfied during the best window of minutes.

  4. We then iterate through each minute i, simultaneously calculating the sliding window sum t for grumpy minutes. We do this by incrementing t by customers[i] only if grumpy[i] == 1.

  5. 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.

  6. We calculate the potential maximum number of satisfied customers ans by subtracting from cs the total dissatisfaction without the current window (s - t). If it exceeds our previous best (ans), we update ans.

  7. After updating ans, we adjust t 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]).

  8. Once the loop is done, all possible windows of size minutes have been checked. The ans 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)).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example 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.

  1. 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.

  2. 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.

  1. 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.

  2. 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 window minutes 4-6 is where the owner is constantly grumpy with customers [10, 1, 10].

  3. 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.

  4. 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.

  5. 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.

  6. 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
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Sliding Window Maximum

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫