Container With Most Water in DSA C

Mental Model

We want to find two lines that hold the most water between them by checking pairs from the edges inward.

Analogy: Imagine two people standing on opposite ends of a riverbank holding a rope. The water they can hold between them depends on the shorter person and the distance between them. Moving the shorter person inward might find a better spot to hold more water.

height array: [1] [8] [6] [2] [5] [4] [8] [3] [7]
indexes:      0    1    2    3    4    5    6    7    8
left pointer ↑                                                                 right pointer ↑

Dry Run Walkthrough

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

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

Step 1: Calculate area between left=0 and right=8

left=0 (height=1), right=8 (height=7), area=1 * (8-0)=8

Why: Start with widest container to get initial max area

Step 2: Move left pointer from 0 to 1 because height[left]<height[right]

left=1 (height=8), right=8 (height=7), area=7 * (8-1)=49

Why: Moving the shorter line might find a taller line and larger area

Step 3: Move right pointer from 8 to 7 because height[right]<height[left]

left=1 (height=8), right=7 (height=3), area=3 * (7-1)=18

Why: Right line is shorter, move it inward to try for bigger area

Step 4: Move right pointer from 7 to 6 because height[right]<height[left]

left=1 (height=8), right=6 (height=8), area=8 * (6-1)=40

Why: Right line is shorter or equal, move it inward to try for bigger area

Step 5: Move left pointer from 1 to 2 because height[left]<height[right]

left=2 (height=6), right=6 (height=8), area=6 * (6-2)=24

Why: Left line is shorter, move it inward

Step 6: Move left pointer from 2 to 3 because height[left]<height[right]

left=3 (height=2), right=6 (height=8), area=2 * (6-3)=6

Why: Left line is shorter, move it inward

Step 7: Move left pointer from 3 to 4 because height[left]<height[right]

left=4 (height=5), right=6 (height=8), area=5 * (6-4)=10

Why: Left line is shorter, move it inward

Step 8: Move left pointer from 4 to 5 because height[left]<height[right]

left=5 (height=4), right=6 (height=8), area=4 * (6-5)=4

Why: Left line is shorter, move it inward

Step 9: Move left pointer from 5 to 6 because height[left]<height[right]

left=6 (height=8), right=6 (height=8), pointers meet, stop

Why: Pointers met, no more containers to check

Result:

Maximum area found is 49 between indexes 1 and 8

Annotated Code

DSA C

#include <stdio.h>

int maxArea(int* height, int heightSize) {
    int left = 0;
    int right = heightSize - 1;
    int max_area = 0;
    while (left < right) {
        int width = right - left;
        int min_height = height[left] < height[right] ? height[left] : height[right];
        int current_area = width * min_height;
        if (current_area > max_area) {
            max_area = current_area;
        }
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

int main() {
    int height[] = {1,8,6,2,5,4,8,3,7};
    int size = sizeof(height) / sizeof(height[0]);
    int result = maxArea(height, size);
    printf("%d\n", result);
    return 0;
}

while (left < right) {

loop until pointers meet to check all container pairs

int width = right - left;

calculate distance between pointers as container width

int min_height = height[left] < height[right] ? height[left] : height[right];

container height limited by shorter line

int current_area = width * min_height;

calculate current container area

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

update max area if current is larger

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

move pointer at shorter line inward to try for bigger area

Output

49

Complexity Analysis

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

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to checking all pairs O(n^2), this two-pointer approach is much faster and efficient

Edge Cases

Empty array

Returns 0 as no container can be formed

DSA C

while (left < right) {

Array with one element

Returns 0 as container needs two lines

DSA C

while (left < right) {

All heights equal

Returns max area as height * (last index - first index)

DSA C

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

When to Use This Pattern

When you need to find max area or max product between pairs in a linear structure, try two pointers from edges moving inward to optimize search.

Common Mistakes

Mistake: Moving the pointer at the taller line instead of the shorter line
Fix: Always move the pointer at the shorter line inward to potentially find a taller line and larger area

Mistake: Calculating area using max height instead of min height
Fix: Use the shorter line height to calculate area because water is limited by the shorter side

Summary

Finds the maximum water container by checking pairs of lines from edges inward.

Use when you want to maximize area between two lines in an array efficiently.

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