[LeetCode] Container With Most Water (Java)

Given n non-negative integers a1a2, …, an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Analysis

It could take a long time if you check every possible container, because the time complexity is $O(n^2)$. So we need another way to achieve it.

We can use two pointers pointing to left and right. Calculate the area formed by left and right pointer. If height of left is smaller than right, we will move left pointer one step, otherwise we will move the right pointer left 1 step. The maximum area is saved during the processing.

When we move the pointer, the width of the area decrease. If the height is smaller than the previous height, then it’s impossible that the area will increase. In other words, if left is shorter than right, no matter how you move your right pointer, you can’t find a area larger than it.

Code

 Complexity

The complexity of this algorithm is $O(n)$.