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 is limited by the shorter person and the distance between them.

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 = min(1,7) * (8-0) = 1*8=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 = min(8,7) * (8-1) = 7*7=49

Why: Moving pointer at smaller height might increase area

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

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

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

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

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

Why: Found equal height, area is large but less than max so far

Step 5: Move right pointer from 6 to 5 because height[left] >= height[right]

left=1 (height=8), right=5 (height=4), area = min(8,4) * (5-1) = 4*4=16

Why: Moving pointer at smaller height might increase area

Step 6: Move right pointer from 5 to 4 because height[left] > height[right]

left=1 (height=8), right=4 (height=5), area = min(8,5) * (4-1) = 5*3=15

Why: Try to find taller line on right side

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

left=1 (height=8), right=3 (height=2), area = min(8,2) * (3-1) = 2*2=4

Why: Continue moving smaller height pointer

Step 8: Move right pointer from 3 to 2 because height[left] > height[right]

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

Why: No better area found, continue moving

Step 9: Move right pointer from 2 to 1, pointers meet, stop

left=1 (height=8), right=1 (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#

using System;

class ContainerWithMostWater {
    public static int MaxArea(int[] height) {
        int left = 0;
        int right = height.Length - 1;
        int maxArea = 0;

        while (left < right) {
            int width = right - left;
            int currentHeight = Math.Min(height[left], height[right]);
            int currentArea = width * currentHeight;
            if (currentArea > maxArea) {
                maxArea = currentArea;
            }

            if (height[left] < height[right]) {
                left++; // move left pointer inward
            } else {
                right--; // move right pointer inward
            }
        }

        return maxArea;
    }

    static void Main() {
        int[] height = {1,8,6,2,5,4,8,3,7};
        int result = MaxArea(height);
        Console.WriteLine(result);
    }
}

while (left < right) {

loop until pointers meet to check all container pairs

int currentHeight = Math.Min(height[left], height[right]);

container height limited by shorter line

int currentArea = width * currentHeight;

calculate current container area

if (currentArea > maxArea) { maxArea = currentArea; }

update max area if current is larger

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

move pointer at smaller height inward to try larger area

Output

49

Complexity Analysis

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

Space: O(1) because we use only a few variables, no extra space proportional to input

vs Alternative: Naive approach checks all pairs with O(n^2) time, this two-pointer method is much faster

Edge Cases

Empty array

Returns 0 as no container can be formed

DSA C#

int right = height.Length - 1; // handles empty by right < left immediately

Array with one element

Returns 0 as container needs two lines

DSA C#

while (left < right) { ... } // loop does not run if left == right

All heights equal

Returns max area as height * (length-1)

DSA C#

maxArea updated inside loop comparing all pairs

When to Use This Pattern

When asked to find max area or max volume between two boundaries in a linear structure, use two pointers from edges moving inward to optimize search.

Common Mistakes

Mistake: Moving both pointers inward at the same time
Fix: Move only the pointer at the smaller height to potentially find a taller line and larger area

Mistake: Calculating area using max height instead of min height
Fix: Use the minimum height of the two pointers to calculate area

Summary

Finds the maximum water container area formed by two lines in an array.

Use when you need to find max area between two boundaries efficiently.

The key is moving the pointer at the smaller height inward to find a potentially taller line.

Practice

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

easy

A. The maximum area of water that can be contained between two lines.

B. The minimum height in the array.

C. The sum of all heights in the array.

D. The number of lines taller than a given height.

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 calculate

   We calculate the area between two lines as the width times the smaller height.

3. Final Answer:

   The maximum area of water that can be contained between two lines. -> Option A

4. Quick Check:

   Container area = width * min(height1, height2) [OK]

Hint: Look for two lines maximizing width and height [OK]

Common Mistakes:

• Thinking it's about sum of heights
• Confusing maximum area with minimum height
• Ignoring width between lines

2. Which of the following is the correct way to declare the main method in a C# program that solves the Container With Most Water problem?

easy

A. void main()

B. public static void Main(string[] args)

C. static Main()

D. public void Main(string args)

Solution

1. Step 1: Recall C# main method syntax

   The main method must be public static void and accept string array args.

2. Step 2: Match options with correct syntax

   public static void Main(string[] args) matches the correct signature: public static void Main(string[] args).

3. Final Answer:

   public static void Main(string[] args) -> Option B

4. Quick Check:

   Main method signature = public static void Main(string[] args) [OK]

Hint: Main method needs public static void with string[] args [OK]

Common Mistakes:

• Using void main() without public static
• Missing string array brackets
• Incorrect parameter type

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

int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
int maxArea = 0;
int left = 0, right = height.Length - 1;
while (left < right) {
    int area = Math.Min(height[left], height[right]) * (right - left);
    if (area > maxArea) maxArea = area;
    if (height[left] < height[right]) left++; else right--;
}
Console.WriteLine(maxArea);

medium

A. 48

B. 49

C. 56

D. 64

Solution

1. Step 1: Understand the two-pointer approach

   Start with left=0 and right=8, calculate area and move pointers inward choosing smaller height side.

2. Step 2: Trace key iterations

   Max area found is 49 between height[1]=8 and height[8]=7 with width 7.

3. Step 3: Continue tracing

   However, a larger area of 56 is found between height[1]=8 and height[6]=8 with width 7.

4. Final Answer:

   56 -> Option C

5. Quick Check:

   Max area = 56 [OK]

Hint: Use two pointers from ends, move smaller height inward [OK]

Common Mistakes:

• Calculating area incorrectly
• Moving wrong pointer
• Not updating maxArea properly

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

int maxArea = 0;
int left = 0, right = height.Length - 1;
while (left <= right) {
    int area = Math.Min(height[left], height[right]) * (right - left);
    if (area > maxArea) maxArea = area;
    if (height[left] < height[right]) left++;
    else right--;
}
return maxArea;

medium

A. maxArea should be initialized to -1 instead of 0.

B. The area calculation should use Math.Max instead of Math.Min.

C. The pointers should both move inward every iteration.

D. The loop condition should be 'left < right' instead of 'left <= right'.

Solution

1. Step 1: Check loop condition

   Using 'left <= right' causes area calculation when left == right, width zero, unnecessary.

2. Step 2: Correct loop condition

   Change to 'left < right' to avoid zero width calculation.

3. Final Answer:

   The loop condition should be 'left < right' instead of 'left <= right'. -> Option D

4. Quick Check:

   Loop must run while left < right [OK]

Hint: Loop until pointers cross, not equal [OK]

Common Mistakes:

• Using <= causes zero width area
• Using Math.Max instead of Math.Min for height
• Moving both pointers each time

5. Given an array of heights, how would you modify the two-pointer approach to find the container with the second largest water area?

hard

A. Track the top two max areas during the pointer moves and return the second largest.

B. Sort the array and pick the two largest heights.

C. Use a nested loop to check all pairs and pick the second largest area.

D. Return the area of the container formed by the first and last lines.

Solution

1. Step 1: Use two-pointer approach with tracking

   While moving pointers, keep track of the largest and second largest areas found.

2. Step 2: Update max and second max areas properly

   When a new area is larger than max, update second max to old max, max to new area; else if area is between max and second max, update second max.

3. Final Answer:

   Track the top two max areas during the pointer moves and return the second largest. -> Option A

4. Quick Check:

   Track max and second max areas during iteration [OK]

Hint: Keep two max values while scanning with two pointers [OK]

Common Mistakes:

• Sorting loses original indices and width info
• Nested loops are inefficient
• Returning first and last lines area only