Links to O(n) solution explanation, and my elaboration


  • 3
    O

    For those who read the articles:

    But you still didn't quite get it, here are some simple thoughts:

    1. We need to at least check all the heights, but do we need to
      check all the choose(n, 2) solutions for each pair of left/right
      boundaries?
    2. If not, when can we be lazy not to check the
      combinations?

    Before start..

    1. left, right represents the left and right boundaries respectively.
    2. Area is decided by (right-left)*min(height[left],height[right])

    Because you are looking for a maximum area,
    you can search from the maximum width (left = 0, right = n - 1)

    Consider the case: height is [1,2,3,4]
    At the beginning, the area would be (3-0) *min(1,4) = 3
    And you find that you would need to check that left = 1, which leads area to be (3-1)*min(2,4) = 4
    and so on...


    But consider the opposite case: height is [4, 3, 2, 1]
    At the beginning, the area would be (3-0) *min(4,1) = 3
    And you do NOT need to move your left bar at all.

    Why? Because the height of area would always bounded by the lowest boundaries.
    For example, at this time, when left = 1, the area would only be (3-1)*min(3,1) = 2


    Here we can draw some conclusion:

    • We can check the left and right alternatively. (What [2] is drawing)
    • If left bar is higher than the right bar, we don't need to move left bar until right bar is higher than the left bar, vise versa. (What [3] is describing)
    • When left bar pass right bar, we've already check all the boundaries.

    These ideas could be proved by the contradiction proof in [1]

    Some sample code in Python:

    class Solution:
    # @param {integer[]} height
    # @return {integer}
    def maxArea(self, height):
        lh, maxArea = len(height), 0
        if lh < 1:
            return 0
        left, right, maxArea = 0, lh-1, 0
        while(left < right):
            maxArea = max(maxArea, (right-left)*min(height[left],height[right]))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return maxArea
    

  • 0
    A

    what i did in this was to have a while loop and move the pointer left or right to next higher element so that area calculation for smaller length is avoided but the solution take more time than this one. Any idea why?


  • 0
    C

Log in to reply
 

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