Container With Most Water
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Pick two vertical lines to form a container with the x-axis; maximise the water it holds.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Water height is limited by the shorter of the two lines.
- Hint 2If you move the taller line inward, can the area ever improve? What if you move the shorter one?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A water tank has two walls of different heights. The water can only rise to the height of the SHORTER wall, or it spills. To get more water you can move walls closer (less width) so you only do that if the new wall is taller. Moving the TALL wall inwards can never help, the short wall still limits the level while width shrinks. So always move the short wall inward and hope for a taller one.
- The obvious way
Try every pair: O(n²).
- The key insight
Start with the widest container. Its height is the shorter wall. Moving the taller wall inward only reduces the width while the height is still capped by the shorter one, so it cannot beat the current area. Therefore move the shorter wall inward and hope for a taller one. Each step discards one wall: O(n).
- The algorithm
- Left pointer on the first wall, right pointer on the last. Best area = 0.
- Area = distance between them x the shorter wall's height. Keep it if it is the best.
- Move the pointer that is on the shorter wall one step inward.
- Repeat until the pointers meet.
Watch it run
Exampleheights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Widest tank: walls 1 and 7, width 8, level 1: area 8. The short wall is 1, move it in.
best area 8
Where people slip
- Move the SHORTER wall; moving the taller one cannot help.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def max_area(heights):
left, right = 0, len(heights) - 1
best = 0
while left < right:
width = right - left
level = min(heights[left], heights[right]) # water rises to the shorter wall
best = max(best, width * level)
if heights[left] < heights[right]:
left += 1 # move the shorter wall
else:
right -= 1
return bestNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.