LeetCode 1052.

Question

There is a bookstore owner that has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array customers of length n where customers[i] is the number of the customer that enters the store at the start of the ith minute and all those customers leave after the end of that minute.

On some 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 of that minute are not satisfied, otherwise, they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for minutes consecutive minutes, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Intuition

The quesiton is tedious and redundant so I first do some transformation:

Calculate the maximum number of customers whom could be satisfied while bookstore owner has a chance to change their attitude on a consecutive number of days.

Approach

declare an array to represent how many customers will be unsatisfied on each day
calculate how many customers will be satisfied due to the bookstore owner’s secret technique on minutes consecutive days
The answer will be addition of the maximum from step 2 and customers whom are satisfied originally

Complexity

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

Code

import java.util.Arrays;

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int n = customers.length;
        int[] notSatisfied = new int[n];
        for (int i=0; i<n; i++) {//n
            notSatisfied[i] = customers[i] * grumpy[i];
        }
        int prev = 0;
        for (int i=0; i<minutes; i++) {//n
            prev += notSatisfied[i];
        }
        int max = prev; 
        for (int i=minutes; i<n; i++) {//n
            prev = prev - notSatisfied[i - minutes] + notSatisfied[i];
            max = Math.max(max, prev);
        }

        for (int i=0; i<n; i++) {//n
            if (grumpy[i] == 0) {
                max += customers[i];
            }
        }
        return max;
    }
}

Check out the description of these two problems at LC 1052.