Container with Most Water

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Return maximum amount of water that can be stored in a container
• Given heights of container

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Two Pointers
• Calculate height
• In the example, shown that water will overflow hence min(wall1, wall2)

Why This Works

(Explain the core reason the solution is correct.)

• You calculate the area and keep a track of the maximum
• Greedily update which wall to move (choose min to move)

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Two Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each item once
• Space: $O(1)$ → Reason: Not storing anything except the two pointers

Code

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        maxArea = 0

        while l < r:
            currentArea = min(height[l], height[r]) * (r-l)
            maxArea = max(maxArea, currentArea)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return maxArea