Container With Most Water in DSA Python

Mental Model

We want to find two lines that hold the most water between them by checking pairs from the edges inward.

Analogy: Imagine two people standing on opposite ends of a riverbank holding a rope. The water they can hold is limited by the shorter person and the distance between them. Moving the shorter person inward might find a better spot to hold more water.

height array: [1] [8] [6] [2] [5] [4] [8] [3] [7]
indexes:      0    1    2    3    4    5    6    7    8
pointers: ↑left                             right↑

Dry Run Walkthrough

Input: height = [1,8,6,2,5,4,8,3,7]

Goal: Find two lines that together with the x-axis form a container holding the most water.

Step 1: Calculate area between left=0 and right=8

left=0 (height=1), right=8 (height=7), area = min(1,7) * (8-0) = 1*8=8

Why: Start with widest container to get a baseline area.

Step 2: Move left pointer from 0 to 1 because height[left] < height[right]

left=1 (height=8), right=8 (height=7), area = min(8,7) * (8-1) = 7*7=49

Why: Moving the shorter line inward might find a taller line and larger area.

Step 3: Move right pointer from 8 to 7 because height[right] < height[left]

left=1 (height=8), right=7 (height=3), area = min(8,3) * (7-1) = 3*6=18

Why: Right line is shorter, so move it inward to try for taller line.

Step 4: Move right pointer from 7 to 6 because height[right] < height[left]

left=1 (height=8), right=6 (height=8), area = min(8,8) * (6-1) = 8*5=40

Why: Right line is still shorter or equal, move inward to find better area.

Step 5: Move left pointer from 1 to 2 because height[left] <= height[right]

left=2 (height=6), right=6 (height=8), area = min(6,8) * (6-2) = 6*4=24

Why: Left line is shorter, move it inward to try for taller line.

Step 6: Move left pointer from 2 to 3 because height[left] < height[right]

left=3 (height=2), right=6 (height=8), area = min(2,8) * (6-3) = 2*3=6

Why: Left line is shorter, move it inward.

Step 7: Move left pointer from 3 to 4 because height[left] < height[right]

left=4 (height=5), right=6 (height=8), area = min(5,8) * (6-4) = 5*2=10

Why: Left line is shorter, move it inward.

Step 8: Move left pointer from 4 to 5 because height[left] < height[right]

left=5 (height=4), right=6 (height=8), area = min(4,8) * (6-5) = 4*1=4

Why: Left line is shorter, move it inward.

Step 9: Move left pointer from 5 to 6, pointers meet, stop

left=6, right=6, pointers meet, end

Why: Pointers crossed, all pairs checked.

Result:

Maximum area found is 49 between lines at index 1 and 8.

Annotated Code

DSA Python

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            width = right - left
            current_area = min(height[left], height[right]) * width
            if current_area > max_area:
                max_area = current_area
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

if __name__ == '__main__':
    height = [1,8,6,2,5,4,8,3,7]
    sol = Solution()
    print(sol.maxArea(height))

while left < right:

loop until pointers meet to check all pairs

current_area = min(height[left], height[right]) * (right - left)

calculate area formed by current pair of lines

if current_area > max_area: max_area = current_area

update max area if current is larger

if height[left] < height[right]: left += 1 else: right -= 1

move pointer at shorter line inward to try for taller line

Output

49

Complexity Analysis

Time: O(n) because we move two pointers inward only once through the list

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Naive approach checks all pairs with O(n^2) time, this two-pointer method is much faster.

Edge Cases

height array with only two lines

Returns area between the two lines directly

DSA Python

while left < right:

height array with all lines of same height

Returns max area using widest distance between lines

DSA Python

if current_area > max_area:

height array with increasing or decreasing heights

Algorithm still finds max area by moving pointers correctly

DSA Python

if height[left] < height[right]:

When to Use This Pattern

When you see a problem asking for max area between two lines or max container, use two pointers from edges moving inward to find the optimal pair efficiently.

Common Mistakes

Mistake: Moving both pointers inward at the same time
Fix: Move only the pointer at the shorter line inward to potentially find a taller line and larger area.

Mistake: Calculating area using max height instead of min height
Fix: Use the minimum height of the two lines to calculate the container area.

Summary

Finds the maximum water container area between two lines using two pointers.

Use when you need to find max area formed by vertical lines and x-axis efficiently.

The key insight is to move the pointer at the shorter line inward to find a potentially taller line and larger area.

Practice

1. What does the problem Container With Most Water ask you to find given an array of heights?

easy

A. The maximum area formed between two vertical lines and the x-axis

B. The minimum height in the array

C. The sum of all heights in the array

D. The number of lines taller than a given height

Solution

1. Step 1: Understand the problem statement

   The problem asks to find two lines that together with the x-axis form a container holding the most water, which means the maximum area between two vertical lines.

2. Step 2: Identify what to calculate

   We calculate the area as the width between two lines multiplied by the smaller height of the two lines.

3. Final Answer:

   The maximum area formed between two vertical lines and the x-axis -> Option A

4. Quick Check:

   Container with most water = maximum area [OK]

Hint: Look for max area between two heights, not sum or count [OK]

Common Mistakes:

• Confusing area with sum of heights
• Looking for minimum height only
• Counting lines instead of calculating area

2. Which of the following is the correct way to initialize two pointers for the Container With Most Water problem in Python?

easy

A. left, right = 1, len(height)

B. left, right = 0, len(height) - 1

C. left = 0; right = len(height)

D. left, right = len(height), 0

Solution

1. Step 1: Understand pointer initialization

   We start with two pointers at the edges of the array: left at 0 and right at the last index, which is length minus one.

2. Step 2: Check each option

   left, right = 0, len(height) - 1 correctly sets left to 0 and right to len(height) - 1. Others either start at wrong indices or exceed array bounds.

3. Final Answer:

   left, right = 0, len(height) - 1 -> Option B

4. Quick Check:

   Start pointers at array ends = left, right = 0, len(height) - 1 [OK]

Hint: Start pointers at first and last index [OK]

Common Mistakes:

• Setting right pointer to len(height) (out of range)
• Starting left pointer at 1 instead of 0
• Swapping left and right initialization

3. What is the output of the following Python code for the Container With Most Water problem?

def max_area(height):
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        width = right - left
        area = min(height[left], height[right]) * width
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

print(max_area([1,8,6,2,5,4,8,3,7]))

medium

A. 49

B. 56

C. 64

D. 72

Solution

1. Step 1: Trace the two-pointer approach

   Start with left=0 (height=1), right=8 (height=7), area = min(1,7)*8=8. Move left pointer since height[left]

2. Step 2: Continue moving pointers and update max_area

   Next left=1 (8), right=8 (7), area = min(8,7)*7=49 (max_area updated). Then right moves left, area decreases. Max area remains 49.

3. Final Answer:

   49 -> Option A

4. Quick Check:

   Max area calculated = 49 [OK]

Hint: Move pointer with smaller height to find max area [OK]

Common Mistakes:

• Calculating area with max height instead of min
• Not updating max_area correctly
• Moving wrong pointer in the loop

4. Find the error in the following code snippet for Container With Most Water and select the fix:

def max_area(height):
    left, right = 0, len(height) - 1
    max_area = 0
    while left <= right:
        width = right - left
        area = min(height[left], height[right]) * width
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

medium

A. Increment both left and right pointers inside the loop

B. Initialize max_area to 1 instead of 0

C. Use max(height[left], height[right]) instead of min

D. Change while condition to 'left < right'

Solution

1. Step 1: Analyze the loop condition

   The loop uses 'while left <= right', which allows left and right to be equal, causing width to be zero and area zero, which is unnecessary.

2. Step 2: Correct the loop condition

   Changing to 'while left < right' ensures pointers do not cross or become equal, avoiding zero width and redundant calculations.

3. Final Answer:

   Change while condition to 'left < right' -> Option D

4. Quick Check:

   Loop until pointers cross, not equal [OK]

Hint: Use 'left < right' to avoid zero width area [OK]

Common Mistakes:

• Using <= causes zero width calculation
• Using max instead of min for height
• Moving both pointers at once

5. Given the heights array [4,3,2,1,4], what is the maximum water container area and which pair of lines form it?

hard

A. 12, formed by lines at indices 1 and 4

B. 9, formed by lines at indices 0 and 3

C. 16, formed by lines at indices 0 and 4

D. 8, formed by lines at indices 2 and 4

Solution

1. Step 1: Calculate area between lines at indices 0 and 4

   Height = min(4,4) = 4, width = 4 - 0 = 4, area = 4 * 4 = 16.

2. Step 2: Check other pairs for larger area

   Pairs (1,4): min(3,4)*3=9; (0,3): min(4,1)*3=3; (2,4): min(2,4)*2=4. None exceed 16.

3. Final Answer:

   16, formed by lines at indices 0 and 4 -> Option C

4. Quick Check:

   Max area = 16 from edges [OK]

Hint: Check edges first, then move inward [OK]

Common Mistakes:

• Ignoring width when calculating area
• Using max height instead of min
• Not checking all pairs properly