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