Grumpy Bookstore Owner

Medium

Nutanix

2 views

Topics:

ArraysSliding Windows

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 i^th 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 i^th 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.length
1 <= minutes <= n <= 2 * 10⁴
0 <= customers[i] <= 1000
grumpy[i] is either 0 or 1.

Try coding it in LeetCode

Grumpy Bookstore Owner

Medium

Nutanix

2 views

Topics:

ArraysSliding Windows

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 i^th 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 i^th 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.length
1 <= minutes <= n <= 2 * 10⁴
0 <= customers[i] <= 1000
grumpy[i] is either 0 or 1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for `customers[i]` and `grumpy[i]`? Can they be negative, zero, or extremely large?
Can the `customers` and `grumpy` arrays be empty or null? What should I return in those cases?
Is `X` always a valid positive integer? What is the maximum possible value of `X`?
If the bookstore owner stays grumpy for the entire duration of the day, should I still consider using `X`?
If multiple solutions exist (different start points for `X` that result in the same maximum satisfaction), is any of them acceptable?

Brute Force Solution

Approach

The brute force method for the Grumpy Bookstore Owner problem involves trying all possible ways to make the bookstore owner happy. We will consider every possible starting point for when the owner uses their trick to be happy, and then see which starting point makes the most customers happy overall.

Here's how the algorithm would work step-by-step:

First, calculate how many happy customers there are without the owner using their special trick.
Now, imagine the owner uses their special ability to make customers happy starting from the first customer and lasting for a certain amount of time.
Calculate how many extra customers are made happy with this starting point.
Do this by checking each customer within that time frame, adding to the total if the customer was previously grumpy.
Repeat steps 2-4, but start from the second customer, then the third, and so on, until you have considered every possible starting customer for the owner's trick.
For each of these starting positions, calculate the total number of happy customers (original happy customers plus those made happy by the trick).
Compare the total happy customers for each starting position and pick the one that results in the highest number of happy customers. This is your answer.

Code Implementation

def grumpy_bookstore_owner_brute_force(customers, grumpy, minutes):

    max_customers_happy = 0

    #Calculate the initial number of happy customers
    initial_happy_customers = 0
    for i in range(len(customers)):
        if grumpy[i] == 0:
            initial_happy_customers += customers[i]

    # Iterate through all possible starting points for the trick
    for start_index in range(len(customers)):
        current_happy_customers = initial_happy_customers

        # Calculate the extra happy customers with the current starting point
        extra_happy = 0
        for i in range(start_index, min(start_index + minutes, len(customers))):
            #Count those grumpy customers made happy by the trick
            if grumpy[i] == 1:
                extra_happy += customers[i]

        #Update the max happy customers
        current_happy_customers += extra_happy
        max_customers_happy = max(max_customers_happy, current_happy_customers)

    return max_customers_happy

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each possible starting point for using the special trick. For each starting point, it iterates through the customers within the specified time frame (customers.length = n). Thus, we have a nested loop where the outer loop iterates up to n times, and the inner loop iterates up to n times in the worst case. Therefore, the total number of operations is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The brute force approach calculates happy customers without using any additional data structures that scale with the input size. It iterates through possible starting points and recalculates happy customers each time, but only uses a fixed number of variables to track the current starting point, the maximum happy customers found so far, and the current number of happy customers. Therefore, the auxiliary space used remains constant irrespective of the number of customers, N, and is O(1).

Optimal Solution

Approach

The core idea is to maximize happy customers by cleverly using the bookstore owner's ability to control their mood for a limited time. We want to identify the best possible window of time to make as many customers happy as possible, considering which ones are normally grumpy.

Here's how the algorithm would work step-by-step:

First, figure out how many customers are already happy without the owner trying to change their mood at all. This will be our baseline.
Next, try using the mood-changing ability on every possible section of customers for the given amount of time. Imagine sliding a window of a certain length across the line of customers.
For each window position, calculate how many *additional* customers you could make happy by changing the owner's mood during that time. Only count the customers who would normally be grumpy.
Keep track of which window position gives you the most *additional* happy customers.
Finally, add the number of additional happy customers from the best window to the initial number of happy customers (our baseline). This is the maximum number of happy customers we can achieve.

Code Implementation

def max_satisfied_customers(customers, grumpy, minutes):
    number_of_customers = len(customers)
    initial_satisfied = 0

    for i in range(number_of_customers):
        if grumpy[i] == 0:
            initial_satisfied += customers[i]

    max_additional_satisfied = 0
    current_additional_satisfied = 0

    # Slide window to maximize additional customers
    for i in range(number_of_customers):
        if grumpy[i] == 1:
            current_additional_satisfied += customers[i]

        if i >= minutes:
            if grumpy[i - minutes] == 1:
                current_additional_satisfied -= customers[i - minutes]

        # Track the sliding window that gives the best result
        max_additional_satisfied = max(max_additional_satisfied, current_additional_satisfied)

    # Total satisfied customers equals initial plus best window
    return initial_satisfied + max_additional_satisfied

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the customers array once to calculate the initial number of happy customers. Then, it uses a sliding window of size X (where X is the given number of minutes) to iterate through the customers array again. For each position of the sliding window, it calculates the additional happy customers within that window. Since the sliding window iterates through the array once and the calculations within each window are constant time operations, the overall time complexity is driven by the single pass through the customers array, resulting in O(n) time complexity where n is the number of customers.

Space Complexity

O(1) – The algorithm primarily uses a sliding window approach, keeping track of the maximum additional happy customers and the current window's sum. No auxiliary data structures that scale with the input size (N, where N is the number of customers) are created. The space used consists of a few integer variables for calculations, resulting in constant extra space.

Edge Cases

Case	How to Handle
customers array is null or empty	Return 0 immediately as no customers are present.
grumpy array is null or empty	Return sum of customers array if S is greater than 0 because grumpy has no effect.
customers and grumpy arrays have different lengths	Throw an IllegalArgumentException or return an error code indicating invalid input.
S is 0, meaning the owner is always grumpy	Return the sum of customers where grumpy[i] is 0 since only those will be satisfied.
S is greater than the length of the arrays	Treat S as the length of the arrays, effectively considering the entire array for maximizing satisfaction.
Large input arrays that could cause integer overflow when calculating sums	Use long data type to store intermediate sums to prevent potential overflows.
All values in the grumpy array are 0	Return the sum of all customer values since the owner is never grumpy.
All values in the grumpy array are 1	Calculate the initial sum, then use sliding window to find the maximum increase possible with the provided S.