Container With Most Water in DSA Go - Execution Trace

Concept Flow - Container With Most Water

Start with two pointers

↓

Calculate area between left and right

↓

Update max area if current area is larger

↓

Move pointer with smaller height inward

↓

left

↓

Repeat until left meets right

↓

Return max area found

Start with two pointers at ends, calculate area, move the smaller height pointer inward, update max area, repeat until pointers meet.

Execution Sample

DSA Go

heights := []int{1,8,6,2,5,4,8,3,7}
left, right := 0, len(heights)-1
maxArea := 0
for left < right {
  area := min(heights[left], heights[right]) * (right - left)
  if area > maxArea { maxArea = area }
  if heights[left] < heights[right] { left++ } else { right-- }
}

Find max water container area by moving two pointers inward, updating max area each step.

Execution Table

Step	Operation	left	right	Height[left]	Height[right]	Width	Area	Max Area	Pointer Moved	Visual State
1	Initialize pointers	0	8	1	7	8	8	8	Move left (1<7)	[1] 8 6 2 5 4 8 3 [7]
2	Calculate area	1	8	8	7	7	49	49	Move right (8>=7)	1 [8] 6 2 5 4 8 3 [7]
3	Calculate area	1	7	8	3	6	18	49	Move right (8>=3)	1 [8] 6 2 5 4 8 [3] 7
4	Calculate area	1	6	8	8	5	40	49	Move right (8>=8)	1 [8] 6 2 5 4 [8] 3 7
5	Calculate area	1	5	8	4	4	16	49	Move right (8>=4)	1 [8] 6 2 5 [4] 8 3 7
6	Calculate area	1	4	8	5	3	15	49	Move right (8>=5)	1 [8] 6 2 [5] 4 8 3 7
7	Calculate area	1	3	8	2	2	4	49	Move right (8>=2)	1 [8] 6 [2] 5 4 8 3 7
8	Calculate area	1	2	8	6	1	6	49	Move right (8>=6)	1 [8] [6] 2 5 4 8 3 7
9	Calculate area	1	1	8	8	0	0	49	Pointers met, stop	1 [8] 6 2 5 4 8 3 7
10	End	-	-	-	-	-	-	49	-	Final max area is 49

💡 Pointers met at left=right=1, loop ends with max area 49

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
left	0	1	1	1	1	1	1	1	1	1
right	8	8	7	6	5	4	3	2	1	1
maxArea	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 depends on the smaller height, moving the taller pointer won't increase area. See steps 1 and 2 in execution_table where left pointer moves when height[left]<height[right].

Why does the loop stop when left meets right?

When left equals right, width becomes zero, so no container can be formed. This is shown in step 9 where left=right=1 and area=0, so loop ends.

Why do we update maxArea only if current area is larger?

We want the largest container, so we keep maxArea as the biggest area found so far. In step 2, area 49 replaces previous maxArea 8, but later smaller areas do not update maxArea.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the maxArea value?

A 8

B 18

C 49

D 0

💡 Hint

Check the 'Max Area' column in row for step 2 in execution_table.

At which step do the pointers meet and the loop stops?

A Step 8

B Step 9

C Step 10

D Step 7

💡 Hint

Look for the step where left equals right in execution_table.

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

A right pointer moves

B both pointers move

C left pointer moves

D no pointer moves

💡 Hint

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

Concept Snapshot

Container With Most Water:
- Use two pointers at array ends
- Calculate area = min(height[left], height[right]) * width
- Update max area if larger
- Move pointer with smaller height inward
- Repeat until pointers meet
- Return max area found

Full Transcript

This concept uses two pointers starting at the ends of the height array. At each step, we calculate the area formed by the lines at these pointers and the distance between them. We keep track of the maximum area found. Then, we move the pointer pointing to the smaller height inward, hoping to find a taller line to increase area. This repeats until the pointers meet, at which point we have found the maximum container area. The execution table shows each step's pointers, heights, area, and max area updates. The variable tracker shows how left, right, and maxArea change over time. Key moments clarify why we move the smaller height pointer and why the loop stops when pointers meet.

Practice

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

easy

A. The sum of all heights

B. The minimum height in the array

C. The maximum area of water that can be contained between two lines

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 which together with the x-axis form a container that holds the most water.

2. Step 2: Identify what to calculate

   We calculate the area between two lines as the width between them times the smaller height.

3. Final Answer:

   The maximum area of water that can be contained between two lines -> Option C

4. Quick Check:

   Container with most water = maximum area [OK]

Hint: Focus on max area between two heights, not sum or count [OK]

Common Mistakes:

• Confusing max area with sum of heights
• Ignoring the smaller height when calculating area
• Thinking about counting lines instead of area

2. Which of the following Go code snippets correctly declares a slice of heights for the Container With Most Water problem?

easy

A. heights := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}

B. heights := [1, 8, 6, 2, 5, 4, 8, 3, 7]

C. heights := (1, 8, 6, 2, 5, 4, 8, 3, 7)

D. heights := {1, 8, 6, 2, 5, 4, 8, 3, 7}

Solution

1. Step 1: Recall Go slice declaration syntax

   In Go, slices are declared using []type{values}, for example []int{1,2,3}.

2. Step 2: Check each option

   heights := []int{1, 8, 6, 2, 5, 4, 8, 3, 7} uses []int{...} which is correct. Options A, B, C use invalid syntax for slices.

3. Final Answer:

   heights := []int{1, 8, 6, 2, 5, 4, 8, 3, 7} -> Option A

4. Quick Check:

   Slice declaration uses []type{values} [OK]

Hint: Use []int{...} to declare slices in Go [OK]

Common Mistakes:

• Using parentheses or braces instead of [] for slices
• Confusing arrays and slices syntax
• Missing type declaration in slice

3. What is the output of the following Go code snippet that implements the Container With Most Water logic?

package main
import "fmt"
func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0
    for left < right {
        width := right - left
        var h int
        if height[left] < height[right] {
            h = height[left]
            left++
        } else {
            h = height[right]
            right--
        }
        area := width * h
        if area > maxArea {
            maxArea = area
        }
    }
    return maxArea
}
func main() {
    heights := []int{1,8,6,2,5,4,8,3,7}
    fmt.Println(maxArea(heights))
}

medium

A. 49

B. 56

C. 48

D. 64

Solution

1. Step 1: Understand the two-pointer approach

   Start with left=0 and right=8, calculate area and move the pointer with smaller height inward.

2. Step 2: Trace the iterations

   Initial area: min(1,7)*8=8 Move left to 1 Next area: min(8,7)*7=49 Move right to 7 Next area: min(8,3)*6=18 Move right to 6 Next area: min(8,8)*5=40 Move right to 5 Next area: min(8,4)*4=16 Move right to 4 Next area: min(8,5)*3=15 Move right to 3 Next area: min(8,2)*2=4 Move right to 2 Next area: min(8,6)*1=1 Move left to 2 Max area found is 49.

3. Final Answer:

   49 -> Option A

4. Quick Check:

   Max area calculated by two-pointer = 49 [OK]

Hint: Use two pointers moving inward, track max area [OK]

Common Mistakes:

• Calculating area with max height instead of min
• Not moving the pointer with smaller height
• Confusing width calculation

4. Identify the bug in this Go function for Container With Most Water and select the fix:

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0
    for left <= right {
        width := right - left
        var h int
        if height[left] < height[right] {
            h = height[left]
            left++
        } else {
            h = height[right]
            right--
        }
        area := width * h
        if area > maxArea {
            maxArea = area
        }
    }
    return maxArea
}

medium

A. Use maxArea = area without checking if area > maxArea

B. Initialize maxArea to -1 instead of 0

C. Increment both left and right pointers inside the loop

D. Change loop condition to 'left < right' instead of 'left <= right'

Solution

1. Step 1: Analyze the loop condition

   The loop runs while left <= right, which allows left and right to be equal, causing width to be zero or negative.

2. Step 2: Fix the loop condition

   Changing to left < right ensures width is always positive and valid for area calculation.

3. Final Answer:

   Change loop condition to 'left < right' instead of 'left <= right' -> Option D

4. Quick Check:

   Loop must run while left < right [OK]

Hint: Use strict less than for pointers to avoid zero width [OK]

Common Mistakes:

• Using <= instead of < causing invalid area
• Updating both pointers at once
• Not checking if area is greater before updating maxArea

5. Given the heights slice []int{4, 3, 2, 1, 4}, what is the maximum water container area? Use the two-pointer approach and explain why the maximum area is found at those positions.

hard

A. 12

B. 16

C. 8

D. 6

Solution

1. Step 1: Initialize pointers and calculate areas

   Start with left=0 (height=4), right=4 (height=4), width=4, area=4*4=16.

2. Step 2: Move pointers and check other areas

   Since heights[left] == heights[right], move right pointer left: Now left=0, right=3 (height=1), width=3, area=min(4,1)*3=3 Move right to 2 (height=2), area= min(4,2)*2=4 Move right to 1 (height=3), area= min(4,3)*1=3 Max area remains 16.

3. Final Answer:

   16 -> Option B

4. Quick Check:

   Max area between positions 0 and 4 = 16 [OK]

Hint: Max area often at widest distance with min height [OK]

Common Mistakes:

• Not considering both ends first
• Moving wrong pointer when heights are equal
• Calculating area incorrectly with wrong width