Container With Most Water in DSA C++

Mental Model

We want to find two lines that hold the most water between them by maximizing the area formed by their heights and the distance between them.

Analogy: Imagine two vertical walls on a beach holding water between them. The water amount depends on the shorter wall and how far apart the walls are.

height array: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Positions:    0  1  2  3  4  5  6  7  8
Water container formed between two lines:
Line i ↑                             ↑ Line j
|                                   |
|                                   |
|                                   |
Distance between i and j is width
Height is min(height[i], height[j])

Dry Run Walkthrough

Input: height array: [1, 8, 6, 2, 5, 4, 8, 3, 7]

Goal: Find two lines that together hold the maximum amount of water.

Step 1: Start with two pointers at the ends: left=0, right=8

Positions: 0[1] -> ... -> 8[7]
Pointers: ↑left                 ↑right

Why: We start with the widest container to maximize width.

Step 2: Calculate area = min(1,7) * (8-0) = 1 * 8 = 8; move left pointer right because height[left]<height[right]

Positions: 1[8] -> ... -> 8[7]
Pointers:    ↑left           ↑right

Why: Moving the shorter line might find a taller line to increase area.

Step 3: Calculate area = min(8,7) * (8-1) = 7 * 7 = 49; move right pointer left because height[right]<height[left]

Positions: 1[8] -> ... -> 7[3]
Pointers:    ↑left       ↑right

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

Step 4: Calculate area = min(8,3) * (7-1) = 3 * 6 = 18; move right pointer left because height[right]<height[left]

Positions: 1[8] -> ... -> 6[8]
Pointers:    ↑left   ↑right

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

Step 5: Calculate area = min(8,8) * (6-1) = 8 * 5 = 40; move left pointer right because height[left]<=height[right]

Positions: 2[6] -> ... -> 6[8]
Pointers:       ↑left   ↑right

Why: Moving left pointer to find taller line or better width.

Step 6: Calculate area = min(6,8) * (6-2) = 6 * 4 = 24; move left pointer right because height[left]<height[right]

Positions: 3[2] -> ... -> 6[8]
Pointers:          ↑left   ↑right

Why: Try to find taller line on left side.

Step 7: Calculate area = min(2,8) * (6-3) = 2 * 3 = 6; move left pointer right because height[left]<height[right]

Positions: 4[5] -> ... -> 6[8]
Pointers:             ↑left   ↑right

Why: Try to find taller line on left side.

Step 8: Calculate area = min(5,8) * (6-4) = 5 * 2 = 10; move left pointer right because height[left]<height[right]

Positions: 5[4] -> 6[8]
Pointers:                ↑left   ↑right

Why: Try to find taller line on left side.

Step 9: Calculate area = min(4,8) * (6-5) = 4 * 1 = 4; move left pointer right because height[left]<height[right]

Positions: 6[8]
Pointers:                   ↑left/right

Why: Pointers meet, end search.

Result:

Maximum area found is 49 between positions 1 and 8.
Final pointers meet at position 6.

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxArea(const vector<int>& height) {
    int left = 0;
    int right = (int)height.size() - 1;
    int max_area = 0;
    while (left < right) {
        int width = right - left;
        int curr_height = min(height[left], height[right]);
        int area = width * curr_height;
        if (area > max_area) {
            max_area = area;
        }
        if (height[left] <= height[right]) {
            left++; // move left pointer right to find taller line
        } else {
            right--; // move right pointer left to find taller line
        }
    }
    return max_area;
}

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

while (left < right) {

loop until pointers meet to check all possible containers

int width = right - left;

calculate distance between two lines

int curr_height = min(height[left], height[right]);

height of water limited by shorter line

int area = width * curr_height;

calculate current container area

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

update max area if current is bigger

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

move pointer at shorter line inward to try to find taller line

Output

49

Complexity Analysis

Time: O(n) because we move two pointers inward only once each, scanning the array once

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Naive approach checks all pairs with O(n^2) time, which is slower for large inputs

Edge Cases

Empty array

Returns 0 because no container can be formed

DSA C++

while (left < right) {

Array with one element

Returns 0 because at least two lines are needed

DSA C++

while (left < right) {

All heights equal

Returns max area as height * (distance between first and last)

DSA C++

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

When to Use This Pattern

When asked to find max area or max product between two elements with distance, use two-pointer approach to optimize from brute force.

Common Mistakes

Mistake: Moving the pointer at the taller line instead of the shorter line
Fix: Always move the pointer at the shorter line to try to find a taller line and possibly increase area

Mistake: Calculating area using max height instead of min height
Fix: Use min(height[left], height[right]) because water is limited by the shorter line

Summary

Find two lines that together hold the most water by maximizing area between them.

Use when you need to find max area between two elements in an array with distance constraint.

The key is moving the pointer at the shorter line inward to find a potentially taller line and maximize area.

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