1052. Grumpy Bookstore Owner - Explanation

Problem Link

Description

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 ith 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 ith 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 = [10,1,7], grumpy = [0,0,0], minutes = 2

Output: 18

Explanation: The bookstore owner is already not grumpy for all the customers.

Constraints:

  • n == customers.length == grumpy.length
  • 1 <= minutes <= n <= 20,000
  • 0 <= customers[i] <= 1000
  • grumpy[i] is either 0 or 1.

Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

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

        satisfied = res
        for i in range(n - minutes + 1):
            cur = 0
            for j in range(i, i + minutes):
                if grumpy[j]:
                    cur += customers[j]
            res = max(res, satisfied + cur)

        return res

Time & Space Complexity

  • Time complexity: O(n∗m)O(n * m)
  • Space complexity: O(1)O(1)

Where nn is the size of the input array and mm is the number of minutes.

2. Sliding Window

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        l = 0
        window = max_window = 0
        satisfied = 0

        for r in range(len(customers)):
            if grumpy[r]:
                window += customers[r]
            else:
                satisfied += customers[r]

            if r - l + 1 > minutes:
                if grumpy[l]:
                    window -= customers[l]
                l += 1

            max_window = max(window, max_window)

        return satisfied + max_window

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)