Container With Most Water in DSA Rust - Execution Trace

Concept Flow - Container With Most Water

Start with two pointers

↓

Calculate area between left and right

↓

Update max area if current is larger

↓

Move pointer with smaller height inward

↓

left

↓

Repeat until left meets right

↓

Return max area

Use two pointers at ends, calculate area, move the smaller height pointer inward, repeat until pointers meet.

Execution Sample

DSA Rust

fn max_area(height: Vec<i32>) -> i32 {
    let (mut left, mut right) = (0, height.len() - 1);
    let mut max_area = 0;
    while left < right {
        let area = (right - left) as i32 * height[left].min(height[right]);
        max_area = max_area.max(area);
        if height[left] < height[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }
    max_area
}

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

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	4	min(1,4)*(8-0)=8	8	Move left (height[left]<height[right])	[1,8,6,2,5,4,8,3,4]
2	Calculate area	1	8	8	4	min(8,4)*(8-1)=28	28	Move right (height[right]<=height[left])	[1,8,6,2,5,4,8,3,4]
3	Calculate area	1	7	8	3	min(8,3)*(7-1)=18	28	Move right	[1,8,6,2,5,4,8,3,4]
4	Calculate area	1	6	8	8	min(8,8)*(6-1)=40	40	Move right	[1,8,6,2,5,4,8,3,4]
5	Calculate area	1	5	8	4	min(8,4)*(5-1)=32	40	Move right	[1,8,6,2,5,4,8,3,4]
6	Calculate area	1	4	8	5	min(8,5)*(4-1)=15	40	Move right	[1,8,6,2,5,4,8,3,4]
7	Calculate area	1	3	8	2	min(8,2)*(3-1)=4	40	Move right	[1,8,6,2,5,4,8,3,4]
8	Calculate area	1	2	8	6	min(8,6)*(2-1)=6	40	Move right	[1,8,6,2,5,4,8,3,4]
9	Calculate area	1	1	8	8	Pointers met, stop	40	None	[1,8,6,2,5,4,8,3,4]

💡 Pointers met at index 1, no more container possible.

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
max_area	0	8	28	28	40	40	40	40	40	40

Key Moments - 3 Insights

Why do we move the pointer with smaller height instead of the larger one?

Because the area is limited by the smaller height, moving the smaller pointer inward may find a taller line and possibly a larger area. See execution_table steps 1 and 2 where moving the smaller height pointer leads to larger max_area.

Why do we stop when left meets right?

When left equals right, the container width is zero, so no area can be formed. 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's 'Area Calculated' column in execution_table.

Visual Quiz - 3 Questions

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

A 28

B 18

C 40

D 16

💡 Hint

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

At which step does the max_area first become 28?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Max Area' column in execution_table to find when it updates to 28.

If the height at left pointer was always greater than right pointer, which pointer moves?

A Right pointer moves

B Left pointer moves

C Both pointers move

D No pointer moves

💡 Hint

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

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 if larger found
- Stop when pointers meet

Full Transcript

This concept uses two pointers starting at the ends of the height array. At each step, it calculates the area formed by the lines at these pointers. The area is the smaller height times the distance between pointers. The pointer at the smaller height moves inward to try to find a taller line and possibly a larger area. This repeats until the pointers meet. The maximum area found during this process is returned. The execution table shows each step's pointers, heights, area, max area, and which pointer moves. Key moments clarify why the smaller pointer moves and why the process 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 maximum area formed between two vertical lines and the x-axis

B. The minimum height in the array

C. The sum of all heights

D. The longest increasing subsequence of heights

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 maximizing the area between them.

2. Step 2: Identify what to calculate

   The area is calculated by the distance between the 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 = max area between lines [OK]

Hint: Look for two lines maximizing width x min height [OK]

Common Mistakes:

• Confusing sum of heights with area
• Choosing tallest lines without considering distance
• Ignoring the smaller height between two lines

2. Which Rust code snippet correctly declares a vector of heights for the Container With Most Water problem?

easy

A. let heights = {1, 8, 6, 2, 5, 4, 8, 3, 7};

B. let heights = vec![1, 8, 6, 2, 5, 4, 8, 3, 7];

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

D. let heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, a vector is declared using vec![...] macro to create a growable array.

2. Step 2: Check each option

   let heights = vec![1, 8, 6, 2, 5, 4, 8, 3, 7]; uses vec![...] correctly. let heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]; is an array, not a vector. let heights = (1, 8, 6, 2, 5, 4, 8, 3, 7); is a tuple. let heights = {1, 8, 6, 2, 5, 4, 8, 3, 7}; uses braces which is invalid syntax.

3. Final Answer:

   let heights = vec![1, 8, 6, 2, 5, 4, 8, 3, 7]; -> Option B

4. Quick Check:

   Vector syntax = vec![...] [OK]

Hint: Use vec![...] for vectors in Rust [OK]

Common Mistakes:

• Using array syntax instead of vector
• Using tuple parentheses instead of brackets
• Using braces which is invalid

3. What is the output of this Rust code snippet that finds the max water container area?

fn max_area(height: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = height.len() - 1;
    let mut max_area = 0;
    while left < right {
        let width = (right - left) as i32;
        let h = if height[left] < height[right] { height[left] } else { height[right] };
        let area = width * h;
        if area > max_area {
            max_area = area;
        }
        if height[left] < height[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }
    max_area
}

fn main() {
    let heights = vec![1,8,6,2,5,4,8,3,7];
    println!("{}", max_area(heights));
}

medium

A. 48

B. 56

C. 64

D. 49

Solution

1. Step 1: Understand the two-pointer approach

   Start with left at 0 and right at last index, calculate area, move pointer with smaller height inward.

2. Step 2: Trace the code with given heights

   Max area found is between height 8 at index 1 and height 7 at index 8, width = 7, area = 7 * 7 = 49.

3. Final Answer:

   49 -> Option D

4. Quick Check:

   Max area = 49 [OK]

Hint: Use two pointers, move smaller height inward [OK]

Common Mistakes:

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

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

fn max_area(height: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = height.len();
    let mut max_area = 0;
    while left < right {
        let width = (right - left) as i32;
        let h = if height[left] < height[right] { height[left] } else { height[right] };
        let area = width * h;
        if area > max_area {
            max_area = area;
        }
        if height[left] < height[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }
    max_area
}

medium

A. Change right initialization to height.len() - 1

B. Change while condition to left <= right

C. Use max instead of min height for area calculation

D. Remove the if condition inside the loop

Solution

1. Step 1: Check initialization of right pointer

   Rust vectors are zero-indexed, so last index is length - 1, not length.

2. Step 2: Identify impact of wrong right pointer

   Using length causes out-of-bounds access when accessing height[right], leading to runtime error.

3. Final Answer:

   Change right initialization to height.len() - 1 -> Option A

4. Quick Check:

   Right pointer = last index = len() - 1 [OK]

Hint: Index last element with len() - 1, not len() [OK]

Common Mistakes:

• Using length as index causing panic
• Changing loop condition incorrectly
• Using max height instead of min for area

5. Given a vector of heights, how would you modify the two-pointer approach to also return the indices of the two lines forming the container with the most water?

hard

A. Return the sum of the two heights instead of area

B. Use a nested loop to check all pairs and store indices of max area

C. Keep track of max_area and update a tuple (left_index, right_index) whenever max_area changes

D. Only return the left pointer index as the answer

Solution

1. Step 1: Understand the two-pointer approach

   We move pointers inward and calculate area at each step, updating max area found.

2. Step 2: Track indices when max area updates

   Along with max_area, store the current left and right indices whenever a larger area is found.

3. Final Answer:

   Keep track of max_area and update a tuple (left_index, right_index) whenever max_area changes -> Option C

4. Quick Check:

   Track indices with max area updates [OK]

Hint: Update indices when max area changes [OK]

Common Mistakes:

• Returning sum instead of area
• Using nested loops losing O(n) efficiency
• Returning only one index instead of both