A LeetCode Daily Series — Day 82

In this article, we will dive into a problem from the world of competitive programming that involves a bookstore owner who can influence customer satisfaction by managing their grumpiness. We’ll explore the problem, understand a brute force approach, and then refine our solution using a more efficient approach. Let’s get started!

Grumpy Bookstore Owner - LeetCode leetcode.com

Can you solve this real interview question? Grumpy Bookstore Owner

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem

The problem involves a bookstore owner who experiences fluctuating moods throughout the day. We are given:

• An integer array customers where customers[i] represents the number of customers entering the store at the ith minute.
• A binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute and 0 otherwise.
• An integer minutes representing the maximum number of consecutive minutes the owner can use a technique to prevent being grumpy.

Our goal is to determine the maximum number of satisfied customers in a day, given the owner can use the technique once to reduce grumpiness for a set period.

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

Brute Force Approach

In the brute force approach, we calculate the total number of satisfied customers for every possible window of minutes where the owner is not grumpy, and then find the maximum satisfaction achieved.

def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
    row = 0
    satisfaction = float('-inf')
    start = 0
    end = start + minutes - 1

    while end < len(customers):
        cur_satis = 0
        for i in range(len(customers)):
            if grumpy[i] == 1 and (i < start or i > end):
                continue
            cur_satis += customers[i]

        satisfaction = max(cur_satis, satisfaction)
        start += 1
        end += 1

    return satisfaction

Explanation

1. Initialize satisfaction to Negative Infinity: This ensures any calculated satisfaction will be larger, setting a proper comparison basis.
2. Slide a Window Across the Array: Start with a window of size minutes from the beginning of the array and slide it across the length of the array.
3. Calculate Satisfaction for Each Window: For each window, calculate the number of satisfied customers by including all non-grumpy minutes and only the grumpy minutes within the window.
4. Update Maximum Satisfaction: Keep track of the maximum satisfaction obtained from all windows.

Time Complexity: O(n ^ 2), where n is the number of minutes. This is due to the nested loop for recalculating satisfaction within each window.

Space Complexity: O(1), as we use a constant amount of extra space.

Using Efficient Approach (Sliding Window)

We can optimize the brute force approach using a sliding window technique. This method will allow us to calculate the maximum number of satisfied customers more efficiently by maintaining a running sum of the window of minutes and adjusting it as the window slides.

def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
    total_sum = 0
    for i in range(len(customers)):
        if grumpy[i] == 0:
            total_sum += customers[i]

    satisfaction = total_sum
    start = 0
    end = start + minutes - 1

    while end < len(customers):
        temp_sum = 0
        for i in range(start, end + 1):
            if grumpy[i] == 1:
                temp_sum += customers[i]

        satisfaction = max(satisfaction, total_sum + temp_sum)

        start += 1
        end += 1

    return satisfaction

Explanation

1. Calculate Total Satisfaction: First, calculate the total number of satisfied customers when no grumpy minutes are adjusted.
2. Initialize a Sliding Window: Start with a window of size minutes at the beginning of the array.
3. Calculate Satisfaction for Each Window: For each window, calculate the additional satisfaction that could be achieved if the grumpy minutes within the window were not grumpy.
4. Update Maximum Satisfaction: Keep track of the maximum satisfaction obtained by considering the base satisfaction plus the additional satisfaction from adjusting grumpy minutes within the current window.

Time Complexity: O(n * minutes), where n is the number of minutes. This is because of the nested loop that recalculates the grumpy customers for each window.

Space Complexity: O(1), as we use a constant amount of extra space.

Using Efficient Approach 2 (Optimized Sliding Window)

The optimized sliding window approach improves upon the previous sliding window technique by maintaining a running sum and dynamically adjusting it as the window slides. This eliminates the need for nested loops and makes the algorithm more efficient.

def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
    total_satisfied = 0

    # Calculate the total satisfaction without using the grumpy window
    for i in range(len(customers)):
        if grumpy[i] == 0:
            total_satisfied += customers[i]

    # Calculate the initial window of size minutes
    max_window_sum = 0
    current_window_sum = 0
    for i in range(minutes):
        if grumpy[i] == 1:
            current_window_sum += customers[i]

    max_window_sum = current_window_sum

    # Slide the window across the array
    start = 1
    end = minutes

    while end < len(customers):
        if grumpy[start - 1] == 1:
            current_window_sum -= customers[start - 1]
        if grumpy[end] == 1:
            current_window_sum += customers[end]

        max_window_sum = max(max_window_sum, current_window_sum)
        start += 1
        end += 1

    return total_satisfied + max_window_sum

Explanation

1. Calculate Total Satisfaction: First, calculate the total number of satisfied customers when no grumpy minutes are adjusted.
2. Initialize a Window of Size minutes: Calculate the sum of grumpy customers within the initial window.
3. Slide the Window Across the Array: As the window slides, dynamically adjust the current window sum by subtracting the customer count from the minute that is left behind and adding the customer count from the new minute that enters the window.
4. Track the Maximum Sum of Grumpy Customers: Keep track of the maximum sum of grumpy customers that can be satisfied within any window.
5. Return Total Satisfaction: Add the total satisfaction (from non-grumpy minutes) to the maximum window sum to get the final result.

Time Complexity: O(n), where n is the number of minutes. This is because we process each element at most twice (once when it enters the window and once when it exits).

Space Complexity: O(1), as we use a constant amount of extra space.

Conclusion

We started with a brute force approach to solve the grumpy bookstore owner problem and then improved our solution using two sliding window techniques. The final optimized sliding window approach drastically reduces the time complexity, making our solution more suitable for larger inputs.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series

A LeetCode Daily Series — Day 83 | Ritesh Shakya riteshakya.com.np

Today’s problem is called "Count Number of Nice Subarrays"