Container With Most Water

🔍 Problem

You're given an array height[], where each element represents the height of a vertical line

draw n on the x-axis at that index.
We want to choose two lines such that, together with the x-axis, they form a container that holds the maximum amount of water.

⛲ How is Water Area Calculated?

For two lines at indices i and j:

The height of the water is the minimum of the two heights: min(height[i], height[j])

The width is the distance between them: j - i

So, the area (water stored) = min(height[i], height[j]) * (j - i)

We need to maximize this area.

🧠 Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation:
Choose height[1] = 8 and height[8] = 7
Area = min(8, 7) * (8 - 1) = 7 * 7 = 49

Example 2

Input: height = [1,1]
Output: 1
(min(1,1) * (1-0) = 1 * 1 = 1)

Example 3:

Input: height = [4,3,2,1,4]
Output: 16
(min(4,4) * (4-0) = 4 * 4 = 16)

💣 Brute Force Approach

🧾 Idea:

Try every pair of lines (i, j) and compute the area for each.

💡 Time Complexity: O(n²)

Algorithm:

Initialize max_area = 0

Loop i from 0 to n-1

Loop j from i+1 to n

For each pair (i,j) compute: area = min(height[i], height[j]) * (j - i)

Update max_area

This is not efficient for large inputs.

⚡ Two Pointer Approach (Optimized)

💡 Time Complexity: O(n)

💾 Space Complexity: O(1)

🧾 Idea:

Use two pointers: one at the start (left), one at the end (right)

Calculate area between them

Move the pointer pointing to the shorter line, since increasing the height may help increase the     area.

✅ Why it works?
The width decreases as we move pointers, so we must look for taller lines to maintain a large area.

🧮 Algorithm Steps (Two Pointer):

Set left = 0, right = n-1, and max_area = 0

While left < right:

Compute area: min(height[left], height[right]) * (right - left)

Update max_area

If height[left] < height[right]: left++

Else: right--

Return max_area

🔠 C++ Code: Two Pointer Approach

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int lp=0,rp=n-1;
        int maxwater=0;
        while(lp<rp){
            int w=rp-lp;
            int ht=min(height[lp],height[rp]);
            int currwidth=w*ht;
            maxwater=max(maxwater,currwidth);
           height[lp]<height[rp] ? lp++ : rp--;

        }
        return maxwater;
    }
};

Java Code: Two Pointer Approach

public class MaxWaterContainer {
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int w = right - left;
            int area = h * w;
            maxArea = Math.max(maxArea, area);

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

        return maxArea;
    }

    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("Maximum Water Area: " + maxArea(height));
    }
}

Python Code: Two Pointer Approach

def max_area(height):
    left = 0
    right = len(height) - 1
    max_area = 0

    while left < right:
        h = min(height[left], height[right])
        w = right - left
        area = h * w
        max_area = max(max_area, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

# Example usage
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print("Maximum Water Area:", max_area(height))

. How do you calculate the area between two lines?

Answer:
Area is calculated using the formula:


Area = min(height[i], height[j]) * (j - i)
The height is the smaller of the two lines.

The width is the distance between them (index difference).

. What is the brute-force approach and its time complexity?

Answer:

Try all possible pairs (i, j) and compute the area.

Keep track of the maximum.

Time complexity: O(n^2)
Space complexity: O(1)

What is the optimized solution and how does it work?

Answer:
Two-pointer approach:

Start with two pointers, one at the beginning and one at the end.

Move the pointer with the smaller height, because moving the taller one won’t help increase area due     to smaller height limiting the water.

Update the maximum area at each step.

Time complexity: O(n)
Space complexity: O(1)

Why move the shorter line's pointer in the two-pointer method?

Answer:
Because the area is limited by the shorter line, so the only way to potentially get a bigger area is     to try a taller line, which we might find by moving the shorter pointer inward.

. Can the container be slanted (i.e., not vertical)?

Answer:
No. The lines must remain vertical and cannot be slanted. You can only form containers using     vertical lines and the x-axis.

. What type of array input would be a worst case for the brute force but not for the two-pointer method?

Answer:
A large array with all heights being equal (e.g., [1,1,1,...,1]). Brute force would check every     pair, but the two-pointer would solve it efficiently by narrowing from both ends.

Approach?

→ Two-pointer

Brute force time?

→ O(n²)

Optimized time?

→ O(n)

Space complexity?

→ O(1)

Area formula?

→ min

Pointer to move?

→ Shorter

ata structure used?

→ Array

Problem type?

→ Greedy

Can container be slanted?

→ No

Height used?

→ Minimum