Leetcode 1052 Grumpy Bookstore Owner

Leetcode 1052 Grumpy Bookstore Owner

https://leetcode.com/problems/grumpy-bookstore-owner/description

When I see the minutes is consecutive, I thought of sliding window immediately. We will iterate all the possible window with the fixed length and see which one produces the max result.

• First we calculate the initial sum of the array with the sliding window sits at between 0 and minutes - 1
• Then we start moving the window
  • Check if the new element that comes in affects the sum and update sum accordingly
  • Check if the element that goes out affects the sum and update sum accordingly
  • Compare the new sum with the existing max value and update it if needed

Let’s take a look at the solution

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        sum = 0
        for i in range(len(grumpy)):
            if i < minutes:
                sum += customers[i]
            else:
                sum += (1 - grumpy[i]) * customers[i]
        
        left, right = 0, minutes
        result = sum
        while right < len(grumpy):
            if grumpy[right]:
                sum += customers[right]
            if grumpy[left]:
                sum -= customers[left]
            
            result = max(sum, result)

            left += 1
            right += 1
        
        return result

The time complexity is O(n) since we iterate the array twice, one for getting the initial sum, the other for the sliding window.