Problem statement

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

Solution

First of all, let as evaluate ans is the number of customers that always satisfied. Also evaluate cost is array of additional customers which can be satisfied with secred technique. All we need to do now is to find the window of length M with the biggest sum in this array. It can be done using sliding window or cumulative sums.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def maxSatisfied(self, arr, G, M):
        ans = sum(x*(1 - y) for x, y in zip(arr, G))
        cost = [x*y for x, y in zip(arr, G)]
        acc = [0] + list(accumulate(cost))
        gain = max(acc[i] - acc[i - M] for i in range(M, len(acc)))
        return ans + gain