# java O(n) top solution with explanation.

• O(n) solution in java. Explanation :
(1) Let's assume that the maxSurface is between offset [0, n-1] is surface = (n-1 - 0) * min(height[n-1], height[0]).
(2) As we move one pointer form 0 to n-1, and one pointer from n-1 0, the distance keep decreasing, as such the surface area keep decreasing if the minimum area remains the same - or lower.
(3) Because of (2) and the formula in (1), only higher minimum heights can produce an higher surface area as the surface length decrease.

``````    public int maxArea(int[] height) {
int maxArea=0;
int x1 = 0, x2 = height.length - 1;
int h = -1; // the max height recorded so far. We haven't computed anything, so let's guess it's -1.
// we validate that x2 > x1 that BOTH new height are higher than the previous minimum height calculated.
while((height[x1] >= h && height[x2] >= h) && x2>x1) {
// we find an higher height, let calcute the new min height, and replace the surface area if necessary.
h = Math.min(height[x1], height[x2]);
int newArea = (x2-x1) * h;
if(maxArea < newArea) maxArea = newArea;

// Now that we have evaluated that a new surface area exist, we need to find a new minimum height by moving x1 and x2 to an height that is higher than the previous one.
while(height[x1] <= h && x2 > x1) x1++;
// we move the offset until the next left hand maxValuePossible.
while(height[x2] <= h && x2 > x1) x2--;
}
return maxArea;
}
````````

• I really like your solution and your explanation is super helpful. I was wondering why you have

``````height[x1] >= h && height[x2] >= h
``````

in your while statement conditional. Would that not always be true?

Also, I struggled a bit understanding the logic behind the pointer moving. The way I thought about it was that there are two conditions:

• two heights are the same, in which case, moving just one pointer will always yield a smaller sum than the original height.
• two heights are different, in which case moving the higher pointer inward will ways yield a smaller sum than the original height.

Thus, you move the pointer with the smaller height. My reasoning is a bit unnecessarily complex, I was wondering if you had a better way of explaining how the pointer movements don't miss any cases in between.

• @tomtang2 You are right, "height[x1] >= h && height[x2] >= h" is not necessary. Forgot to remove it.

For each bucket, surface = width * minimumHeight. We calculate an initial surface given an arbitrary max width. We save the minimum height (let's call it current_minimum_height)

We potentially increase x1 and potentially decrease x2 so that they satisfy the following condition : x1 >= current_minimum_height, x2 >= current_minimum_height.

• two heights are the same : then two pointers move so that both of them are higher than the previous height.
• heights are different : only the smaller height until it's new value is superior to the old one.

e.g.

[5, 0, 6, 1, 10, 0 7]

-iteration 1 : We need to find a new higher height so that x1 >= 0 and x2 >=0

``````[5, 0, 8, 1, 10, 0, 7] maxArea = 0
|                  |
x1[0]             x2[6]
``````

x1[0][5],x2[6][7] - Minimum heights is at x1 = 5. Surface is 5*(6-0) = 30;

-iteration2 : We need to find a new higher height so that x1 >= 5 and x2 >=5. (x2 does not move as it already satisfies the condition)

``````[5, 0, 8, 1, 10, 0, 7] maxArea = 30
>>  |            |
x1[2]        x2[6]
``````

x1[2][8], x2[6][7] - Minimum height is at x2 = 7 Surface area : (6-2)*7 = 28 (<30)

-iteration3 : We need to find a new higher height so that x1 >= 7 and x2 >= 7 (x1 does not move as it already satisfies the condition)

``````[5, 0, 8, 1, 10, 0, 7] maxArea = 30
|      |  <<
x1[2]  x2[4]
``````

x1[2][8], x2[4][10] - minimum height x1 = 8 Surface area : (6-4)*8 = 16 (<30).

-x2 > 8. x1 will now move to find a new minimum height, but will reach x2 (breaking the condition).
-We return the max surface area = 30.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.