Product-based companies like Google, Amazon, and Microsoft have started hiring students for their problem-solving abilities rather than just programming skills. Be it online assessments, technical rounds, or interviews they are gradually refraining from asking questions directly. Questions that are a combination of daily activities and programming concepts like dynamic programming, recursion, etc are being asked quite frequently. One such question that is gaining popularity around the subject is Container with Most Water. Today, we'll be discussing this problem, its approach, and how you can devise its solution. So, let's get started!
You are given an array 'height' having 'n' non-negative integers. 'n' vertical lines are drawn so that the ending points of the ith line are (I,0) and (i, height[I]). Your task is to find the two lines forming a container that contains the most water inside it. Return the amount of water inside them.
Note: You cannot slant the container.
Let's take a look at the below image to understand how the output came out to be 20.
We have given 2 approaches to solve this question: the brute force method and the optimal solution. Although the first method works perfectly fine, its time complexity is longer than the second one. See for yourself!
Method 1: Brute Force Approach
The first naive approach that comes into our mind is called Brute Force Approach. It's not efficient yet we get the answer. The main idea here is to return the maximum area between the two lines, and observe that even though containers have a volume of water, you cannot express the answer as volume since we're in a 2D plane. Therefore, we need to find the area.
Now, what determines the area? Its length and breadth. Hence, here we'll check each element pairing with the next element in the loop and calculate the area between them. If the area is larger than the previous one, we'll update it. Finally, the answer will be displayed as the output.
Create a nested loop with the elements specified below and a variable for calculating the area:
Inner Loop Counter - inCount ; Outer Loop Counter - outCount ; Area Variable - maxWater
Now, the outCount moves from 0 to the end of the height array (n), and the inCount from outCount+1 to the end. At every iteration, calculate the water(area) between the 2 counter variables and store it in the maxWater variable. While moving ahead, if the value of maxWater becomes more than its previous value, update its value. Later, return the answer.
area= (inCount-outCount) * min(height[inCount] * height[outCount]).
The time complexity of this method is O(n^2). Why? Because we are using a nested loop and the counter variables traverse over the array twice, making it x2.
During this whole program, we are not creating any other array or data structure so its space complexity remains constant O(1).
Method 2: Optimal Approach
The previous approach was using a nested loop, therefore the time complexity was O(n^2). What if there was a better solution that performed the same work in lesser time? Let's take a look at this solution.
In this method, we take 2 variables that point towards the beginning and end of the given array respectively. We set a particular condition at which the first or second variable will move. At the point where the state breaks, we get our answer. Let's see how we can solve this question using this approach.
Declare two variables, first=0 and end=n-1, and another variable called maxWater to store the answer(most water in a container). Now, calculate the water between the first and end, taking them as two lines. But, there is a possibility that a greater amount of water is there in other containers. So, you increase the first variable by 1 if height[first] < height[end], otherwise you bring the end variable towards the left by 1. This will ensure you get the right answer by finding out the maximum water and ruling out all the possible answers.
The time complexity here reduces to O(n), making it more efficient than the previous one. Why? Since it does all the checking in a single go, the time gets reduced.
As we are not using any extra space, just like the previous solution, here also it remains constant.
C++ Code for Finding Container With Most Water
Java Code for Finding Container With Most Water
Python Code for Finding Container With Most Water
In this competitive world with more than 23 million software developers, having a cutting edge over other students is crucial for you to land in a product-based company. Companies like Microsoft, Meta, etc are expecting their future employees to have efficient programming skills. Therefore, going for optimal solutions is a good way to ensure your presence at a good company. We, at FavTutor, bring to you the most complex questions with the easiest approach so that you can get not just the solution but the intuition behind it too!