Container With Most Water in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the 'Container With Most Water' problem?

To find two lines in an array that, together with the x-axis, form a container holding the maximum amount of water.

intermediate

Why do we use two pointers in the optimal solution for 'Container With Most Water'?

Two pointers start at both ends and move inward to efficiently check all possible containers without checking every pair, reducing time complexity to O(n).

intermediate

In the two-pointer approach, which pointer do we move and why?

We move the pointer at the shorter line inward because moving the longer line won't increase the container size; the height is limited by the shorter line.

beginner

What is the time complexity of the two-pointer solution for 'Container With Most Water'?

O(n), where n is the number of lines, because each pointer moves at most n times.

beginner

Show the formula to calculate the area of water contained between two lines at positions i and j.

Area = min(height[i], height[j]) * (j - i), where height[i] and height[j] are the heights of the lines and (j - i) is the distance between them.

What does the 'Container With Most Water' problem ask you to maximize?

A The sum of heights of all lines

B The distance between the two tallest lines

C The area between two lines and the x-axis

D The number of lines used

The problem asks to find two lines that form a container with the maximum area of water.

In the two-pointer method, where do the pointers start?

A One at the start and one at the end

B Both at the end of the array

C Both at the start of the array

D Random positions

Pointers start at both ends to check the widest container first and then move inward.

Why do we move the pointer at the shorter line in the two-pointer approach?

A Because the longer line is always better

B Because the shorter line limits the container height

C To increase the distance between pointers

D To decrease the area

The container's height is limited by the shorter line, so moving it may find a taller line and increase area.

What is the time complexity of the two-pointer solution?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

The two-pointer approach checks each line at most once, resulting in linear time complexity.

Which of these is the correct formula for the container area between lines i and j?

A max(height[i], height[j]) * (j - i)

B height[i] * height[j]

C height[i] + height[j] + (j - i)

D min(height[i], height[j]) * (j - i)

Area is calculated by the shorter height times the distance between the lines.

Explain the two-pointer approach to solve the 'Container With Most Water' problem.

Think about how moving the shorter line pointer can help find a bigger container.

Describe why the two-pointer method is more efficient than checking all pairs of lines.

Consider how many pairs there are and how two pointers reduce that.

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