Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2

Input: customers = [1], grumpy = [0], minutes = 1
Output: 1

Solution

Method 1 - Sliding Window

  1. Calculate the Customers Satisfied When Not Grumpy: First, identify all the customers who are satisfied when the owner is not grumpy.
  2. Sliding Window to Use the Secret Technique: Use a sliding window of size minutes to calculate the maximum additional customers that can be satisfied by using the technique to make the owner not grumpy for these consecutive minutes.
  3. Combine Results: The result will be the sum of customers who are always satisfied (when the owner is not grumpy) and the best segment where the technique can be applied to maximize the number of satisfied customers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Solution {

	public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
		int n = customers.length;
		int totalSatisfied = 0;

		// Calculate the number of customers satisfied when the owner is not grumpy
		for (int i = 0; i < n; i++) {
			if (grumpy[i] == 0) {
				totalSatisfied += customers[i];
			}
		}

		int currentExtraSatisfied = 0;

		// Calculate the additional satisfied customers
		// for the first 'minutes' window
		for (int i = 0; i < minutes; i++) {
			if (grumpy[i] == 1) {
				currentExtraSatisfied += customers[i];
			}
		}

		// Use sliding window to find the maximum 
		// extra customers that can be satisfied
		int maxExtraSatisfied = currentExtraSatisfied;

		// Move the window across the array
		for (int i = minutes; i < n; i++) {
			if (grumpy[i] == 1) {
				currentExtraSatisfied += customers[i];
			}

			if (grumpy[i - minutes] == 1) {
				currentExtraSatisfied -= customers[i - minutes];
			}

			maxExtraSatisfied = Math.max(maxExtraSatisfied, currentExtraSatisfied);
		}

		// Return the total satisfied customers including the best segment
		return totalSatisfied + maxExtraSatisfied;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)