Container With Most Water in DSA Java - Execution Trace

Concept Flow - Container With Most Water

Start with two pointers

↓

Calculate area between left and right

↓

Compare with max area, update if larger

↓

Move pointer with smaller height inward

↓

left++ if height[left

↓

Repeat until left meets right

↓

Return max area found

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

Execution Sample

DSA Java

int maxArea(int[] height) {
  int left = 0, right = height.length - 1;
  int maxArea = 0;
  while (left < right) {
    int area = Math.min(height[left], height[right]) * (right - left);
    maxArea = Math.max(maxArea, area);
    if (height[left] < height[right]) left++; else right--;
  }
  return maxArea;
}

Calculates max water container area by moving two pointers inward based on heights.

Execution Table

Step	Operation	left	right	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[right]<=height[left])	[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[right]<=height[left])	[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[right]<=height[left])	[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[right]<=height[left])	[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[right]<=height[left])	[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[right]<=height[left])	[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[right]<=height[left])	[1,8,6,2,5,4,8,3,7]
9	Pointers meet	1	1	8	8	-	49	Stop	[1,8,6,2,5,4,8,3,7]

💡 Pointers meet at index 1, loop ends.

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 is limited by the smaller height, moving the larger height pointer won't increase area. See steps 1 and 2 in execution_table where left moves when height[left]<height[right].

Why does the loop stop when left meets right?

When left equals right, no container can be formed between two different lines. 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)?

The water container's height is limited by the shorter line, and width is the distance between pointers. This formula is used in every step's 'Area Calculated' column.

Visual Quiz - 3 Questions

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

A 18

B 21

C 15

D 32

💡 Hint

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

At which step does the right pointer first move?

A Step 1

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Pointer Moved' column in execution_table for the first 'Move right'.

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

A Left pointer moves

B Right pointer moves

C Both pointers move simultaneously

D No pointer moves

💡 Hint

Refer to the condition in the code and pointer movement in execution_table.

Concept Snapshot

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

Full Transcript

This visual execution traces the Container With Most Water problem. We start with two pointers at the ends of the height array. At each step, we calculate the area formed by the lines at these pointers using the formula min(height[left], height[right]) times the distance between pointers. We update the maximum area found so far. Then, we move the pointer pointing to the smaller height inward, because moving the larger height pointer cannot increase the area. This process repeats until the two pointers meet, at which point the maximum area found is returned. The execution table shows each step's pointer positions, heights, area calculated, max area updated, and which pointer moves. The variable tracker shows how left, right, and maxArea change over time. Key moments clarify why the smaller pointer moves and why the loop stops. The visual quiz tests understanding of these steps.

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