• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:


Today the neighborhood bar is open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the bar, and all those customers leave after the end of that minute.

On some minutes, the bartender is grumpy. If the bartender is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bartender is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bartender knows a secret technique to keep herself 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.

Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bartender keeps herself not grumpy for the last 3 minutes. The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Solution:


Prerequisite: Sliding Window Core Concept

If you have noticed, for Sliding Window based problems we are not following any template. Instead, what I want you to focus on is logical thinking keeping fundamental approach of Sliding Window technique in mind. Sliding Window at its heart is very simple: (1) we keep two pointers to keep track of the window, and (2) we expand it and shrink it as necessary.

At any time i whenever grumpy[i] = 0, no matter what the customers are satisfied whether the bartender uses secret technique or not. So, at the minimum: number of satisfied customers = summation of customers[i] for all i for which grumpy[i] = 0 . So what matters now is to look for an X minutes window, when you get satisfied customers for each of these X minutes since the bartender is using the secret technique, which would maximize the overall number of satisfied customers. Let's now quickly code it up. I will add more details in the inline comments as I code. But before you jump on to see the code, I fervently request you to take a pen and paper (or, on a whiteboard) and write down pseudocode for the algorithm and code up a quick implementation. You can even use an IDE and come up with your own test cases to test your code.
The implementation approach of Sliding Window sounds very simple (keeping two pointers to keep track of the window and expanding and shrinking it as necessary) but believe me when you write your first Sliding Window based implementation, things often go awry. It's sometimes good to learn from your own experience rather than other's experiences. This is the very reason I want you to try to write up the code yourself first just to see where you get stuck. If you look at the code below after going through this exercise you'd learn a ton more and you'd have a long-lasting hands-on knowledge and a deeper understanding.
I can't emphasize enough how important it is to test your code in a coding interview even before your interviewer asks you to do so.

Java Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




If you are beginner, the above code would look perfectly fine to you, but a little more experienced developer would not be satisfied with the above code and would demand a little more optimization, which often results in lesser number of code lines without compromising the readability. This often differentiates a good coder from an average one, and my goal is to make you not just a good coder but an exceptional one, over time. You may not be impressed by the Python code I write since I am not a Python developer. The most I do with Python script and Flask is to write necessary scripts to deploy Machine Learning models at scale, and that's it. But I strongly believe that you can learn a ton from the Java code. I will try to discuss various software engineering best practices and the art of writing clean code every now and then in between discussing algorithms.

In the below code we won't write a separate loop to initialize additionalSatisfiedCustomersUsingSecretTechniqueInCurrentWindow, rather we would use just one while loop.

Java Code:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave