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.

Practice

1. What does the problem Container With Most Water ask you to find given an array of heights?

easy

A. The number of lines taller than a given height

B. The minimum height in the array

C. The sum of all heights in the array

D. The maximum area formed between two lines representing container walls

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.

2. Step 2: Identify what to maximize

   We want to maximize the area between two lines, which is the width between them times the smaller height.

3. Final Answer:

   The maximum area formed between two lines representing container walls -> Option D

4. Quick Check:

   Max area = max water container [OK]

Hint: Focus on max area between two heights, not sum or count [OK]

Common Mistakes:

• Confusing max area with sum of heights
• Looking for minimum height only
• Counting lines instead of calculating area

2. Which of the following is the correct way to declare the two-pointer variables for solving Container With Most Water in C?

easy

A. int left = 1, right = n;

B. int left = n, right = 0;

C. int left = 0, right = n - 1;

D. int left = -1, right = n + 1;

Solution

1. Step 1: Understand pointer initialization

   We start with left pointer at the start (index 0) and right pointer at the end (index n-1) of the array.

2. Step 2: Check each option

   int left = 0, right = n - 1; correctly initializes left=0 and right=n-1. Others use invalid or out-of-bound indices.

3. Final Answer:

   int left = 0, right = n - 1; -> Option C

4. Quick Check:

   Two pointers at array ends = int left = 0, right = n - 1; [OK]

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

Common Mistakes:

• Starting pointers out of array bounds
• Using 1-based indexing in C arrays
• Swapping left and right initialization

3. What is the output of the following C code snippet for the array height = {1, 8, 6, 2, 5, 4, 8, 3, 7}?

int maxArea(int* height, int heightSize) {
    int left = 0, right = heightSize - 1, max_area = 0;
    while (left < right) {
        int area = (right - left) * (height[left] < height[right] ? height[left] : height[right]);
        if (area > max_area) max_area = 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]);
    printf("%d", maxArea(height, size));
    return 0;
}

medium

A. 72

B. 49

C. 64

D. 56

Solution

1. Step 1: Initialize pointers and max_area

   left=0, right=8, max_area=0. Calculate area each step and update max_area.

2. Step 2: Trace iterations

   left=0 (1), right=8 (7), area=8*1=8, max=8, left++; left=1 (8), right=8 (7), area=7*7=49, max=49; next areas smaller (e.g. 6*3=18, 5*8=40), max_area remains 49.

3. Final Answer:

   49 -> Option B

4. Quick Check:

   Max water container area = 49 [OK]

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

Common Mistakes:

• Calculating area incorrectly as sum instead of width*height
• Not updating max_area properly
• Moving wrong pointer in the loop

4. Identify the bug in this C code snippet for Container With Most Water and select the fix:

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

medium

A. Change while condition to left < right

B. Initialize max_area to -1

C. Use max_area += area instead of max_area = area

D. Swap left and right pointers initialization

Solution

1. Step 1: Analyze loop condition

   The loop uses while(left <= right), which allows left == right, causing zero width and unnecessary calculation.

2. Step 2: Correct loop condition

   Change condition to while(left < right) to avoid zero width and infinite loop risk.

3. Final Answer:

   Change while condition to left < right -> Option A

4. Quick Check:

   Loop must run while left < right [OK]

Hint: Use strict less than for pointers to avoid zero width [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Incorrectly updating max_area by adding
• Changing pointer initialization unnecessarily

5. Given an array of heights representing vertical lines, how would you modify the two-pointer approach to find the container with the most water if the container must include the line at index 0?

hard

A. Fix left pointer at 0 and move right pointer from end towards left

B. Fix right pointer at 0 and move left pointer from start towards right

C. Use a nested loop to check all pairs including index 0

D. Use binary search to find max area including index 0

Solution

1. Step 1: Understand the constraint

   The container must include the line at index 0, so left pointer stays fixed at 0.

2. Step 2: Move right pointer from end to left

   Move right pointer from the last index towards 1, calculating area with fixed left pointer to find max area.

3. Final Answer:

   Fix left pointer at 0 and move right pointer from end towards left -> Option A

4. Quick Check:

   Fix one pointer at 0, move other to find max area [OK]

Hint: Fix one pointer, move the other to maximize area [OK]

Common Mistakes:

• Moving left pointer instead of fixing it
• Using nested loops unnecessarily
• Applying binary search incorrectly