Python solution with detailed explanation


  • 0
    G

    Solution

    Algorithms

    • Brute force solution tests every pair and computes the container with most water.
    class Solution_BruteForce(object):
        def maxArea(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            N = len(height)
            max_water = -1
            for i in range(N):
                for j in range(i+1,N):
                    max_water = max(max_water, min(height[i], height[j])*(j-i))
            return max_water
    

    Two Pointer

    • O(N) solution which is explained in editorial. Why the solution works needs some thought.
    • Use two pointers start and end initialized at 0 and N-1
    • Now compute the area implied by these pointers as (end-start) * min (height[start], height[end])
    • if height[start] < height[end], start = start + 1 else end = end -1
    • Why? Imagine height[start] < height[end]. Then is there any need to compare height[end-1] with height[start]? There is no way we can now get a larger area using height[start] as one of the end points. We should therefore move start.
      https://discuss.leetcode.com/topic/3462/yet-another-way-to-see-what-happens-in-the-o-n-algorithm/2
    class Solution(object):
        def maxArea(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            s, e = 0, len(height)-1
            max_water = -1
            while s < e:
                max_water = max(max_water, (e-s)*min(height[s], height[e]))
                if height[s] < height[e]:
                    s = s+1
                else:
                    e = e-1
            return max_water
    

Log in to reply
 

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