Container With Most Water in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Pointer Approach for Container With Most Water

What is the output of the following C++ code that finds the maximum water container area using the two-pointer technique?

DSA C++

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int max_area = 0;
    while (left < right) {
        int width = right - left;
        int h = min(height[left], height[right]);
        int area = width * h;
        max_area = max(max_area, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

int main() {
    vector<int> height = {1,8,6,2,5,4,8,3,7};
    cout << maxArea(height) << endl;
    return 0;
}

A 56

B 50

C 48

D 49

💡 Hint

Think about the widest container with the shortest height limiting the water.

The maximum area is found between the lines at index 1 (height 8) and index 8 (height 7). The width is 7, height is min(8,7)=7, so area = 7*7=49.

🧠 Conceptual

intermediate

Understanding the Two Pointer Movement

In the two-pointer approach for the Container With Most Water problem, why do we move the pointer pointing to the shorter line inward?

A Because moving any pointer randomly will eventually find the max area.

B Because moving the taller line pointer cannot increase the area since width decreases and height is limited by the shorter line.

C Because moving the taller line pointer always increases the area.

D Because moving the shorter line pointer decreases the width faster.

💡 Hint

Think about what limits the water container height.

The area is limited by the shorter line. Moving the taller line pointer inward cannot increase area because width decreases and height is still limited by the shorter line. Moving the shorter line pointer may find a taller line and possibly a bigger area.

🔧 Debug

advanced

Identify the Error in Container With Most Water Implementation

What error will the following C++ code produce when compiled or run?

DSA C++

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int max_area = 0;
    while (left <= right) {
        int width = right - left;
        int h = min(height[left], height[right]);
        int area = width * h;
        max_area = max(max_area, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

A Runs correctly and returns the max area

B Runs but returns incorrect max area

C Runtime error due to invalid index access

D Compilation error due to missing headers

💡 Hint

Check the loop condition carefully.

The loop condition 'left <= right' allows an extra iteration when left == right, causing width to be zero and area zero for that iteration. This does not cause runtime error and does not affect the correctness of the max area, as zero area won't update the maximum. The code runs correctly.

❓ Predict Output

advanced

Output of Modified Container With Most Water Code

What is the output of this modified C++ code that uses a different approach to find the max water container?

DSA C++

int maxArea(vector<int>& height) {
    int max_area = 0;
    for (int i = 0; i < height.size(); i++) {
        for (int j = i + 1; j < height.size(); j++) {
            int area = (j - i) * min(height[i], height[j]);
            max_area = max(max_area, area);
        }
    }
    return max_area;
}

int main() {
    vector<int> height = {1,8,6,2,5,4,8,3,7};
    cout << maxArea(height) << endl;
    return 0;
}

A 49

B 56

C 48

D 50

💡 Hint

This is the brute force approach checking all pairs.

This brute force approach checks all pairs and finds the max area 49 between indices 1 and 8.

🚀 Application

expert

Maximum Water Container with Height Updates

You have an array representing heights of vertical lines. You receive queries to update the height at a specific index and then find the maximum water container area after each update. Which data structure or algorithm approach is best suited to efficiently handle these queries?

A Use a hash map to store heights and find max area by sorting keys after each update.

B Recompute max area from scratch using two-pointer approach after each update.

C Use a segment tree or binary indexed tree to update heights and query max area efficiently.

D Use a stack to keep track of heights and calculate max area after each update.

💡 Hint

Think about data structures that support fast updates and range queries.

Segment trees or binary indexed trees allow efficient updates and queries on ranges, suitable for dynamic height updates and max area queries.

Practice

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

easy

A. Find two lines that together with the x-axis form a container holding the most water

B. Sort the array of heights in ascending order

C. Find the maximum height in the array

D. Calculate the sum of all heights

Solution

1. Step 1: Understand the problem statement

   The problem asks to find two vertical lines which, together with the x-axis, form a container that holds the maximum amount of water.

2. Step 2: Identify what is being maximized

   The area between two lines is calculated by the minimum height of the two lines multiplied by the distance between them. We want to maximize this area.

3. Final Answer:

   Find two lines that together with the x-axis form a container holding the most water -> Option A

4. Quick Check:

   Goal = Max water container [OK]

Hint: Max area = min height * width between lines [OK]

Common Mistakes:

• Thinking it's about sorting heights
• Trying to sum heights instead of area
• Looking for max single height only

2. Which of the following C++ code snippets correctly initializes two pointers for the two-pointer approach in the Container With Most Water problem?

easy

A. int left = 1, right = heights.size();

B. int left = 0, right = heights.size() - 1;

C. int left = 0, right = heights.size();

D. int left = 1, right = heights.size() - 1;

Solution

1. Step 1: Understand pointer initialization

   We start with two pointers: one at the beginning (index 0) and one at the end (index size-1) of the array.

2. Step 2: Check each option

   int left = 0, right = heights.size() - 1; correctly sets left = 0 and right = size - 1, which are valid indices. Other options use invalid indices or off-by-one errors.

3. Final Answer:

   int left = 0, right = heights.size() - 1; -> Option B

4. Quick Check:

   Pointers start at ends = int left = 0, right = heights.size() - 1; [OK]

Hint: Start pointers at array ends: 0 and size-1 [OK]

Common Mistakes:

• Using size() as index (out of bounds)
• Starting pointers at 1 instead of 0
• Swapping left and right initialization

3. What is the output of the following C++ code snippet?

std::vector<int> heights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
int left = 0, right = heights.size() - 1;
int maxArea = 0;
while (left < right) {
    int height = std::min(heights[left], heights[right]);
    int width = right - left;
    maxArea = std::max(maxArea, height * width);
    if (heights[left] < heights[right]) {
        left++;
    } else {
        right--;
    }
}
std::cout << maxArea << std::endl;

medium

A. 56

B. 50

C. 48

D. 49

Solution

1. Step 1: Trace the two-pointer approach

   Start with left=0 (height=1), right=8 (height=7), area= min(1,7)*8=8. Move left pointer since height[left]

2. Step 2: Continue updating maxArea

   Next left=1 (8), right=8 (7), area= min(8,7)*7=49 (maxArea=49). Move right pointer since height[left]>height[right]. Then left=1, right=7 (3), area= min(8,3)*6=18 (maxArea=49). Move right pointer. Continue similarly until pointers meet. The maximum area found is 49.

3. Final Answer:

   49 -> Option D

4. Quick Check:

   Max area = 49 [OK]

Hint: Move pointer at smaller height to find max area [OK]

Common Mistakes:

• Not updating maxArea correctly
• Moving wrong pointer after comparison
• Calculating area with max height instead of min

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

int maxArea(std::vector<int>& heights) {
    int left = 0, right = heights.size();
    int max_area = 0;
    while (left < right) {
        int height = std::min(heights[left], heights[right]);
        int width = right - left;
        max_area = std::max(max_area, height * width);
        if (heights[left] < heights[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

medium

A. The loop condition should be left <= right

B. Use max instead of min to calculate height

C. right should be initialized to heights.size() - 1

D. Increment right instead of decrementing

Solution

1. Step 1: Check pointer initialization

   right is initialized to heights.size(), which is out of bounds since valid indices go up to size()-1.

2. Step 2: Correct initialization and loop condition

   right should be heights.size() - 1 to point to the last valid element. The loop condition left < right is correct.

3. Final Answer:

   right should be initialized to heights.size() - 1 -> Option C

4. Quick Check:

   Index out of bounds fixed by right should be initialized to heights.size() - 1 [OK]

Hint: Array indices go from 0 to size-1 [OK]

Common Mistakes:

• Using size() as index causing runtime error
• Changing loop condition incorrectly
• Using max instead of min for height

5. Given an array of heights representing vertical lines, how would you modify the two-pointer approach to find the maximum water container if the array can contain zero heights (lines with zero height)?

hard

A. Skip zero height lines by moving pointers inward until non-zero heights are found

B. Treat zero heights as normal and proceed with the standard two-pointer approach

C. Remove zero height lines from the array before processing

D. Use a nested loop to check all pairs instead of two-pointer

Solution

1. Step 1: Understand zero height impact

   Lines with zero height cannot hold water, so including them wastes time and area calculations.

2. Step 2: Modify two-pointer approach

   Skip zero height lines by moving pointers inward until both point to non-zero heights. Then apply the standard two-pointer logic to maximize area.

3. Final Answer:

   Skip zero height lines by moving pointers inward until non-zero heights are found -> Option A

4. Quick Check:

   Skip zeros for max area [OK]

Hint: Ignore zero heights by moving pointers inward [OK]

Common Mistakes:

• Processing zero height lines as normal
• Removing elements changes indices and complicates logic
• Switching to nested loops loses efficiency