11. Container With Most Water

Problem Link

Area of container would be determined by two factors: -> width and -> minimum height from its edges. To find the maximum area, we can iterate over different container ends using two loops and select the container with maximum area value, but this approach uses \(O(n^2)\) runtime.

Instead, we can greedily start the iteration from the large available width i.e. either ends of array using two pointers. To move onto next optimal candidate, we can remove the shorter edge, as this would be always the limiting factor in area calculation -> \((r-l)*min(height[l],height[r])\). Also, the solution from shorter edges has been already considered in current iteration, so we don't have to worry about missing the current area in result.

Pseudocode

• Iterate over the array using two pointers, left and right.
• During each iteration, calculate the area covered and update the global result if we've found larger value.
• Later we can just shift the left or right pointers to move onto next candidate to find global maxima.

Runtime Complexity

Time: \(O(n)\), since we're only iterating the nums array once.

Space: \(O(1)\), constant space from pointer variables.

PythonGo

class Solution:
    def maxArea(self, height: List[int]) -> int:
        result = 0
        l, r = 0, len(height)-1
        while l < r:
            curr = (r-l)*min(height[l], height[r])
            result = max(result, curr)
            if height[r] > height[l]:
                l+=1
            else:
                r-=1
        return result

func maxArea(height []int) int {
    l, r := 0, len(height)-1
    var result int
    for l < r {
        curr := (r - l) * min(height[l], height[r])
        result = max(result, curr)
        if height[r] > height[l] {
            l++
        } else {
            r--
        }
    }
    return result
}

---