Container With Most Water in DSA Python - Execution Trace

Concept Flow - Container With Most Water

Start with two pointers

↓

Calculate area between pointers

↓

Compare with max area

↓

Move pointer with smaller height inward

↓

Repeat until pointers meet

↓

Return max area found

We use two pointers at the ends of the array, calculate area, update max, then move the smaller pointer inward until they meet.

Execution Sample

DSA Python

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

This code finds the maximum water container area by moving two pointers inward and calculating areas.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Height[left]	Height[right]	Area Calculated	Max Area	Pointer Moved	Visual State
1	Initialize pointers	0	8	1	7	min(1,7)*8=8	8	Move left (height[left]<height[right])	[1,8,6,2,5,4,8,3,7]
2	Calculate area	1	8	8	7	min(8,7)*7=49	49	Move right (height[left]>=height[right])	[1,8,6,2,5,4,8,3,7]
3	Calculate area	1	7	8	3	min(8,3)*6=18	49	Move right (height[left]>=height[right])	[1,8,6,2,5,4,8,3,7]
4	Calculate area	1	6	8	8	min(8,8)*5=40	49	Move right (height[left]>=height[right])	[1,8,6,2,5,4,8,3,7]
5	Calculate area	1	5	8	4	min(8,4)*4=16	49	Move right (height[left]>=height[right])	[1,8,6,2,5,4,8,3,7]
6	Calculate area	1	4	8	5	min(8,5)*3=15	49	Move right (height[left]>=height[right])	[1,8,6,2,5,4,8,3,7]
7	Calculate area	1	3	8	2	min(8,2)*2=4	49	Move right (height[left]>=height[right])	[1,8,6,2,5,4,8,3,7]
8	Calculate area	1	2	8	6	min(8,6)*1=6	49	Move right (height[left]>=height[right])	[1,8,6,2,5,4,8,3,7]
9	Pointers meet or cross	1	1	8	8	-	49	Stop	[1,8,6,2,5,4,8,3,7]

💡 Pointers meet at index 1, loop ends with max area 49

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
left	0	1	1	1	1	1	1	1	1	1
right	8	8	7	6	5	4	3	2	1	1
max_area	0	8	49	49	49	49	49	49	49	49

Key Moments - 3 Insights

Why do we move the pointer with the smaller height?

Because the area is limited by the smaller height, moving the larger height pointer won't increase area. See steps 1 and 2 in execution_table where moving the smaller height pointer leads to larger area.

Why does the loop stop when left meets right?

When pointers meet, there is no width between them, so area is zero. The exit_note and step 9 in execution_table show this stopping condition.

Why do we calculate area as min(height[left], height[right]) * (right - left)?

Because water container height is limited by the shorter line, and width is the distance between pointers. This formula is used in every step in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the area calculated?

A 42

B 21

C 15

D 10

💡 Hint

Check the 'Area Calculated' column at step 6 in execution_table.

At which step does the max_area first become 49?

A Step 2

B Step 3

C Step 5

D Step 4

💡 Hint

Look at the 'Max Area' column in execution_table to find when it first reaches 49.

If height[left] was always greater than height[right], which pointer would move?

A Left pointer moves

B Right pointer moves

C Both pointers move

D Neither pointer moves

💡 Hint

Refer to the 'Pointer Moved' column in execution_table where height[left]>=height[right] leads to right pointer moving.

Concept Snapshot

Container With Most Water:
- Use two pointers at array ends
- Calculate area = min(height[left], height[right]) * distance
- Move pointer with smaller height inward
- Update max area each step
- Stop when pointers meet
- Returns max water container area

Full Transcript

This visualization shows how the Container With Most Water problem is solved using two pointers. We start with pointers at both ends of the height array. At each step, we calculate the area formed by the lines at these pointers and update the maximum area found. We then move the pointer pointing to the smaller height inward, hoping to find a taller line and a larger area. This process repeats until the pointers meet. The execution table tracks each step's pointers, heights, area calculation, and pointer movement. Key moments clarify why we move the smaller pointer and why the loop stops when pointers meet. The visual quiz tests understanding of area calculations and pointer movements. The concept snapshot summarizes the approach in simple steps.

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