Container With Most Water in DSA Go

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.

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

Dry Run Walkthrough

Input: height array: [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, area = min(1,7) * (8-0) = 1*8=8

left=0 (height=1), right=8 (height=7), max_area=8

Why: Start with widest container, area limited by shorter line at left

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

left=1 (height=8), right=8 (height=7), max_area=8

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

Step 3: Calculate area between left=1 and right=8, area = min(8,7)*(8-1)=7*7=49

left=1, right=8, max_area=49

Why: Found bigger area, update max_area

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

left=1 (height=8), right=7 (height=3), max_area=49

Why: Move shorter line inward to try to find taller line

Step 5: Calculate area between left=1 and right=7, area = min(8,3)*(7-1)=3*6=18

left=1, right=7, max_area=49

Why: Area smaller than max_area, no update

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

left=1 (height=8), right=6 (height=8), max_area=49

Why: Move shorter line inward

Step 7: Calculate area between left=1 and right=6, area = min(8,8)*(6-1)=8*5=40

left=1, right=6, max_area=49

Why: Area smaller than max_area, no update

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

left=1 (height=8), right=5 (height=4), max_area=49

Why: Move shorter line inward

Step 9: Calculate area between left=1 and right=5, area = min(8,4)*(5-1)=4*4=16

left=1, right=5, max_area=49

Why: Area smaller than max_area, no update

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

left=1 (height=8), right=4 (height=5), max_area=49

Why: Move shorter line inward

Step 11: Calculate area between left=1 and right=4, area = min(8,5)*(4-1)=5*3=15

left=1, right=4, max_area=49

Why: Area smaller than max_area, no update

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

left=1 (height=8), right=3 (height=2), max_area=49

Why: Move shorter line inward

Step 13: Calculate area between left=1 and right=3, area = min(8,2)*(3-1)=2*2=4

left=1, right=3, max_area=49

Why: Area smaller than max_area, no update

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

left=1 (height=8), right=2 (height=6), max_area=49

Why: Move shorter line inward

Step 15: Calculate area between left=1 and right=2, area = min(8,6)*(2-1)=6*1=6

left=1, right=2, max_area=49

Why: Area smaller than max_area, no update

Step 16: Move right pointer from 2 to 1, pointers meet, stop

left=1, right=1, max_area=49

Why: No more pairs to check

Result:

left=1 (height=8) and right=8 (height=7) form max container
1 -> 8 -> 6 -> 2 -> 5 -> 4 -> 8 -> 3 -> 7
max_area = 49

Annotated Code

DSA Go

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]
        } else {
            h = height[right]
        }
        area := h * width
        if area > maxArea {
            maxArea = area
        }
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxArea
}

func main() {
    height := []int{1,8,6,2,5,4,8,3,7}
    fmt.Println(maxArea(height))
}

left, right := 0, len(height)-1

initialize two pointers at array ends

for left < right {

loop until pointers meet

width := right - left

calculate width between pointers

if height[left] < height[right] { h = height[left] } else { h = height[right] }

choose shorter height to limit water

area := h * width

calculate current container area

if area > maxArea { maxArea = area }

update max area if current is bigger

if height[left] < height[right] { left++ } else { right-- }

move pointer at shorter line inward to try bigger area

Output

49

Complexity Analysis

Time: O(n) because we scan the array once with two pointers moving inward

Space: O(1) because only a few variables are used regardless of input size

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

Edge Cases

empty array

returns 0 because no container can be formed

DSA Go

left, right := 0, len(height)-1

array with one element

returns 0 because at least two lines are needed

DSA Go

for left < right {

all heights equal

returns max area as height * (length-1)

DSA Go

if area > maxArea { maxArea = area }

When to Use This Pattern

When you need to find max area or max product between pairs in an array and the problem involves two ends, use two pointers moving inward to optimize from O(n^2) to O(n).

Common Mistakes

Mistake: Moving the pointer at the taller line instead of the shorter line
Fix: Always move the pointer at the shorter line inward to potentially find a taller line and larger area

Summary

Finds the maximum water container formed by two lines in an array.

Use when you want to maximize area between two vertical lines efficiently.

The key is moving the pointer at the shorter line inward to explore better options.

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