Problem Overview
Difficulty: Medium
LeetCode Pattern: Two Pointers
You're given a list of heights. Each height represents a vertical line on a graph. All the lines are next to each other, and the width between two lines is 1.
Find two heights that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Example
Input:
· height = [1,8,6,2,5,4,8,3,7]
Output:
· 49
Explanation: Max area of water (blue section) is 7x7 = 49.Quick Video Solution
Step 1: Clarify Requirements
Can the input array be empty?
No, it won’t be empty.
Can it have only one element?
No, it will have at least two.
Can it contain negative elements?
No, heights will be non-negative.
Step 2: Discuss Approaches
1/ Nested Loop (Brute Force)
Logic:
Use a nested loop
For each line:
Calculate area w/ all other lines
Keep track of max area
Return the max area in the end
Big O:
Time: O(n²)
Space: O(1)
2/ Two-Pointers (Optimal)
Logic:
Start with two pointers:
left pointer
right pointer
While left < right:
Calculate container area:
x = right - left
y = min of two heights
area = x*y
Update max area if needed
Move the pointer of shorter line
Return the max area in the end
Big O:
Time: O(n)
Space: O(1)
Step 3: Write Code
Python
Java
C++
Step 4: Answer Follow-Ups
What if the input list is empty?
Max area will be 0.
What if input had negative heights?
Throw appropriate exception.
👨💻 Need Interview Practice?
Book a 1:1 with me
Book Here: Booking URL