java O(n) top solution with explanation.


  • 0
    J

    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;
        }
    ``

  • 0
    T

    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.


  • 1
    J

    @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]
    *(Let's assume this notation [index][value], I like to think about this as coordinates).

    -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.


Log in to reply
 

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