Algorithm Breakdown – Container With Most Water

Container With Most Water (Problem #11) on the popular competitive programming site LeetCode [leetcode.com] is called “Container With Most Water.” The question prompt is as follows: “Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.”

A Visualization of “Container With Most Water” (leetcode.com)

Solving this problem does not require any special data structures or algorithms to solve; instead requiring a little bit of intuition. Consider the situation where you look at the amount of water contained between the two outermost vertical lines. The one on the left is height 1 and the one on the right is height 7. As a result, the maximum area that can be held between the two vertical lines is 1×8 where 8 is the distance between the two vertical lines on the plot.

Notice how the 1 unit tall vertical line is hindering the area of water held within the two lines. No matter what other line you choose to pair with 1 you will find yourself producing a smaller total area (since the height 7 line is as far as you can get from 1). In comparison, there is plenty of opportunity to increase the total area held between two blocks if you were to keep the 7 unit high vertical line and discard the 1 unit high line. This is exactly where the key intuition comes into play.

By always discarding the smaller of the two lines, you are inherently choosing the only option that has opportunity for growth. Discarding the larger of the two only stands to worsen your situation. I have implemented this solution in Go and tested it against the LeetCode test cases to verify that it is indeed a correct solution. Feel free to look over the code and contact me at [contact@thornewolf (dot) com] if you have any questions.

Check out the problem itself at https://leetcode.com/problems/container-with-most-water/

This piece was originally published on Feb. 13, 2020 in Horizons Newspaper, the student-run publication from the Embry-Riddle Aeronautical University's Prescott campus.