Leetcode Weekly Contest 138 - 1052. Grumpy Bookstore Owner

Problem

Today, the bookstore owner has a store open for customers.length minutes.  Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy.  If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0.  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 X minutes straight, but can only use it once.

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

How to solve

Brute force

Simply go through the customer array and whenever the owner is grumpy, check whether it's possible to use X here. Of course this won't be accepted (Time Limit Exceeded).

Two pass

To improve on the previous solution, we can try to avoid an extra loop whenever the owner is grumpy. Instead of a loop, whenever we save the index and the customer whenever the owner is grumpy. Later, we can go back to check when the use of X is maximised by tracking the interval using a queue.

One pass

How can we do better? From the previous solution, we notice that we don't really need to go back and track the indexes in a queue. We can instead

• Go through the array once, keeping track of the maximised potential when the owner is grumpy.
• Instead of a queue, we can simply track the maximum value using a variable. Check the code for details.