Largest Container: Finding Two Walls That Hold the Most Water

Largest Container

Imagine a row of vertical walls standing on the ground. Each wall has a certain height. If you pick any two walls, the space between them can hold water — like a tank with two side walls. The flat ground (the x-axis) is the bottom of the tank.

Your job is to choose the two walls that, together with the ground, can hold the most water, and report how much water that is.

What the input looks like

You are given an array called heights. Each value tells you the height of one wall:

• heights[i] is the height of the wall standing at position i.
• The position i is also the wall's spot along the ground, going left to right.

So the array is both *how tall* each wall is and *where* it stands.

How much water can two walls hold?

Pick two walls, one at index i and one at index j, where i is to the left of j (so i < j). The water they trap forms a rectangle. To find its area, we need its width and its height.

Width is how far apart the walls are:

width = j - i

Height of the water is the tricky part. Water would spill over the shorter wall, so the water level can only rise as high as the smaller of the two walls. That gives us:

height = min(heights[i], heights[j])

Putting both together, the full formula is:

Area = min(heights[i], heights[j]) * (j - i)

The word min just means "the smaller of the two numbers."

A small example

Say heights = {1, 8, 6, 2, 5, 4, 8, 3, 7} (positions 0 to 8).

Let's try the wall at index 1 (height 8) and the wall at index 8 (height 7):

• width = 8 - 1 = 7
• height = min(8, 7) = 7
• Area = 7 * 7 = 49

That is a lot of water! A taller-but-narrower pair, or a wide-but-short pair, would hold less. The best answer balances how tall the shorter wall is against how far apart the walls are.

Why the shorter wall matters

This is the key idea, so let's make it stick. If one wall is very tall but its partner is short, the water still pours out over the short one. So a tall wall is wasted if its partner is short. The "good" pairs are ones where both walls are reasonably tall and they are far apart.

A few things to keep in mind

• i must always be on the left, j on the right: i < j.
• The input is guaranteed to have more than one element, so there are always at least two walls to choose from.
• You want the maximum area over every possible pair of walls.

The function you write

You fill in this function. It receives the wall heights and should return the largest container area:

class Solution {
public:
    int largestContainer(vector<int> &heights) {

    }
};

The simplest way to think about it: try every pair (i, j), compute its area with the formula above, and keep track of the largest area you have seen. That always gives the right answer, and it is a perfectly good place to start before learning faster tricks.