Container With Most Water in DSA Java

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 at the ends of a riverbank holding a rope. The water they can hold is limited by the shorter person and the distance between them. Moving inward, we try to find a better pair that can hold more water.

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

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

Why: Start with widest container to get initial max area

Step 2: Move left pointer from 0 to 1 because height at left is smaller

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

Why: Moving pointer at smaller height might find taller line and larger area

Step 3: Move right pointer from 8 to 7 because height at right is smaller

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

Why: Try to find taller line on right side to increase area

Step 4: Move right pointer from 7 to 6 because height at right is smaller

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

Why: Found taller line, calculate area

Step 5: Move left pointer from 1 to 2 because height at left is smaller

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

Why: Try to find taller line on left side

Step 6: Move left pointer from 2 to 3 because height at left is smaller

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

Why: Continue moving smaller height pointer

Step 7: Move left pointer from 3 to 4 because height at left is smaller

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

Why: Try to find better area

Step 8: Move left pointer from 4 to 5 because height at left is smaller

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

Why: No better area found, continue moving

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

left=6, right=6, end

Why: Pointers met, all pairs checked

Result:

Maximum area found is 49 between indexes 1 and 8

Annotated Code

DSA Java

public class ContainerWithMostWater {
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int width = right - left;
            int currentHeight = Math.min(height[left], height[right]);
            int area = width * currentHeight;
            if (area > maxArea) {
                maxArea = area;
            }
            if (height[left] < height[right]) {
                left++; // move left pointer inward
            } else {
                right--; // move right pointer inward
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] height = {1,8,6,2,5,4,8,3,7};
        int result = maxArea(height);
        System.out.println(result);
    }
}

while (left < right) {

loop until pointers meet to check all pairs

int currentHeight = Math.min(height[left], height[right]);

choose smaller height as container height limits water

int area = width * currentHeight;

calculate current container area

if (area > maxArea) { maxArea = area; }

update max area if current is larger

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

move pointer at smaller height inward to try larger area

Output

49

Complexity Analysis

Time: O(n) because we move two pointers inward at most n times

Space: O(1) because we use only a few variables, no extra space proportional to input

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 as no container can be formed

DSA Java

while (left < right) {

array with one element

returns 0 as at least two lines are needed

DSA Java

while (left < right) {

all heights equal

returns max area as height * (length-1)

DSA Java

if (area > maxArea) { maxArea = area; }

When to Use This Pattern

When you see a problem asking for max area between two lines in an array, use two pointers from edges moving inward to find max container efficiently.

Common Mistakes

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

Mistake: Calculating area using max height instead of min height
Fix: Use the minimum of the two heights because water is limited by the shorter line

Summary

Finds two lines in an array that form the container holding the most water.

Use when you need to maximize area between two vertical lines in a list.

The key is moving pointers inward from edges, always moving the smaller height pointer.

Practice

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

easy

A. The minimum height of the lines in the array.

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

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

2. Step 2: Identify what to maximize

   We want to maximize the area between two lines, which is the width between them times the smaller height.

3. Final Answer:

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

4. Quick Check:

   Max area = max water container [OK]

Hint: Look for two lines maximizing min height * distance [OK]

Common Mistakes:

• Confusing maximum area with sum of heights
• Ignoring the smaller height between two lines
• Thinking it's about counting lines

2. Which of the following is the correct way to declare the two-pointer variables for solving the Container With Most Water problem in Java?

easy

A. int left = 0, right = heights.length;

B. int left = 1, right = heights.length;

C. int left = 1, right = heights.length - 1;

D. int left = 0, right = heights.length - 1;

Solution

1. Step 1: Understand array indexing in Java

   Arrays start at index 0, so the left pointer should start at 0.

2. Step 2: Set right pointer to last index

   The right pointer should be at the last element, which is length - 1.

3. Final Answer:

   int left = 0, right = heights.length - 1; -> Option D

4. Quick Check:

   Array indices start at 0 [OK]

Hint: Start pointers at 0 and length-1 for arrays [OK]

Common Mistakes:

• Starting pointers at 1 instead of 0
• Using length instead of length - 1 for last index
• Confusing array length with last index

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

int[] heights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
int left = 0, right = heights.length - 1;
int maxArea = 0;
while (left < right) {
    int height = Math.min(heights[left], heights[right]);
    int width = right - left;
    maxArea = Math.max(maxArea, height * width);
    if (heights[left] < heights[right]) {
        left++;
    } else {
        right--;
    }
}
System.out.println(maxArea);

medium

A. 49

B. 56

C. 48

D. 50

Solution

1. Step 1: Initialize pointers and maxArea

   left=0, right=8, maxArea=0

2. Step 2: Iterate and calculate areas

   Calculate areas step-by-step: - left=0, right=8: min(1,7)=1, width=8, area=8, maxArea=8 - left=1, right=8: min(8,7)=7, width=7, area=49, maxArea=49 - left=1, right=7: min(8,3)=3, width=6, area=18, maxArea=49 - left=1, right=6: min(8,8)=8, width=5, area=40, maxArea=49 - left=1, right=5: min(8,4)=4, width=4, area=16, maxArea=49 - left=1, right=4: min(8,5)=5, width=3, area=15, maxArea=49 - left=1, right=3: min(8,2)=2, width=2, area=4, maxArea=49 - left=1, right=2: min(8,6)=6, width=1, area=6, maxArea=49 Loop ends when left >= right. This misses some pointer moves. Let's trace fully: - Start: left=0, right=8 area = min(1,7)*8=8 heights[left] left++ => left=1 - left=1, right=8 area = min(8,7)*7=49 heights[left]>heights[right] => right-- => right=7 - left=1, right=7 area = min(8,3)*6=18 heights[left]>heights[right] => right-- => right=6 - left=1, right=6 area = min(8,8)*5=40 heights[left]==heights[right] => right-- => right=5 - left=1, right=5 area = min(8,4)*4=16 heights[left]>heights[right] => right-- => right=4 - left=1, right=4 area = min(8,5)*3=15 heights[left]>heights[right] => right-- => right=3 - left=1, right=3 area = min(8,2)*2=4 heights[left]>heights[right] => right-- => right=2 - left=1, right=2 area = min(8,6)*1=6 heights[left]>heights[right] => right-- => right=1 - left=1, right=1 loop ends Max area found is 49. But the maximum area for this input is actually 49. However, 56 is 56, which is incorrect. Let's check if 56 is possible: - Between indices 1 and 6: min(8,8)*5=40 - Between indices 1 and 8: min(8,7)*7=49 - Between indices 2 and 8: min(6,7)*6=36 - Between indices 1 and 7: min(8,3)*6=18 - Between indices 0 and 8: min(1,7)*8=8 No 56 found. Therefore, correct answer is 49 -> 49.

3. Final Answer:

   49 -> Option A

4. Quick Check:

   Max area found = 49 [OK]

Hint: Move pointer with smaller height inward [OK]

Common Mistakes:

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

4. Identify the bug in the following Java code snippet for the Container With Most Water problem:

int[] heights = {1, 2, 4, 3};
int left = 0, right = heights.length - 1;
int maxArea = 0;
while (left <= right) {
    int height = Math.min(heights[left], heights[right]);
    int width = right - left;
    maxArea = Math.max(maxArea, height * width);
    if (heights[left] < heights[right]) {
        left++;
    } else {
        right--;
    }
}
System.out.println(maxArea);

medium

A. The pointers should both start at 0.

B. The width calculation should be right + left.

C. The loop condition should be left < right, not left <= right.

D. The maxArea should be initialized to Integer.MAX_VALUE.

Solution

1. Step 1: Analyze loop condition

   The loop runs while left <= right, which allows left == right, meaning width = 0.

2. Step 2: Understand impact on area calculation

   When left == right, width = 0, so area is zero and unnecessary iteration occurs. The correct condition is left < right to avoid zero width.

3. Final Answer:

   The loop condition should be left < right, not left <= right. -> Option C

4. Quick Check:

   Loop must stop before pointers meet [OK]

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

Common Mistakes:

• Using <= instead of < in loop condition
• Incorrect width calculation
• Wrong initialization of maxArea

5. Given an array of heights representing vertical lines, how would you modify the two-pointer approach to find the container with the most water if the lines can only be chosen at even indices?

hard

A. Initialize pointers at the first and last even indices, then move inward skipping odd indices.

B. Use a nested loop to check all pairs of even indices only.

C. Ignore the even index condition and apply the standard two-pointer approach.

D. Sort the array and then apply the two-pointer approach.

Solution

1. Step 1: Adjust pointers to even indices

   Start left pointer at index 0 (first even index) and right pointer at the last even index (length-1 or length-2 depending on parity).

2. Step 2: Move pointers inward skipping odd indices

   When moving pointers, increment or decrement by 2 to stay on even indices only.

3. Step 3: Calculate area as usual

   Calculate area using min height and width between pointers, update max area accordingly.

4. Final Answer:

   Initialize pointers at the first and last even indices, then move inward skipping odd indices. -> Option A

5. Quick Check:

   Restrict pointers to even indices [OK]

Hint: Move pointers by 2 to stay on even indices [OK]

Common Mistakes:

• Using standard two-pointer without skipping odd indices
• Sorting array which changes line positions
• Using nested loops causing higher complexity