Container With Most Water - LeetCode Solution

Hi there, welcome to the Weekend LeetCode series for Software Engineering interviews!

Question: You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

LeetCode: https://leetcode.com/problems/container-with-most-water/

Solution: Two Pointers
If we just have two lines that form a container, we know that the maximum height of water in that container will be line with minimum height!

Now in this question, we need to find two lines from the given set of lines such that container formed stores the maximum water — we need to maximize the width of container formed as well!

We can start with considering the first line and last line that will have the maximum width. We will be able to calculate the water that can be stored in the container formed by these lines. Now we need to reduce the width for checking other pair of lines! — to do that we can discard the smaller line as we know that smaller one will lead to less water level.

While doing this, we will also be calculating the water stored in the container formed by the lines in each iteration and storing the max we have calculated up till now!

Lets see an example:
Input: [1, 9, 2, 6]

Considering line at index l: 0 (height: 1) and at index r: 3(height: 6):
Area of container formed by l and r: 3
Max area calculated up till now including this: 3
Line at l has smaller height, so discarding it for next iteration!

Considering line at index l: 1 (height: 9) and at index r: 3(height: 6):
Area of container formed by l and r: 12
Max area calculated up till now including this: 12
Line at r has smaller height, so discarding it for next iteration!

Considering line at index l: 1 (height: 9) and at index r: 2(height: 2):
Area of container formed by l and r: 2
Max area calculated up till now including this: 12
Line at r has smaller height, so discarding it for next iteration!

Time Complexity: O(N) — we iterate through each line in input in the worst case. Worst case will be when the lines are in ascending or descending order of their heights!
Space Complexity: O(1)
[N is the length of height array, i.e., number of lines in input]

Java Code:

Java Code

Thanks for reading up till this point! Don’t forget to comment in case you find any issues or have any suggestions! — We will be posting our leetcode solutions with explanations to interview questions every weekend! Let’s get better at software engineering interviews together!

Please follow us for more content!
Medium: https://medium.com/@thedisguisedcode

Instagram: https://www.instagram.com/thedisguisedcode/