A capacity-planning chart plots hourly headroom as vertical bars at hour 0..n-1. Ops wants the largest rectangle of slack two hours can hold: the shorter bar times the hours between them. The first version nested every pair of hours. A week of data looked instant. A year of hourly bars was still looping when the dashboard timed out.

Area is the shorter wall times the gap between indexes. An array already gives height[i] at x-coordinate i. Nested search visits every pair and still pays O(n²). Opposite-end two pointers drop a side on each step because the width only shrinks.

This is an interview writeup, not a procedure lecture. The two-pointers post owns the left/right walk. Here we only care about which pointer moves when the walls are unequal.

The problem

Given an int[] height, treat index i as a vertical line of height height[i]. Pick two distinct indexes i < j so that min(height[i], height[j]) * (j - i) is as large as possible, and return that area. The water sits in a rectangle: the height is the shorter wall, not a slanted surface between unequal walls.

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]  →  49
         lines i=1 (h=8) and i=8 (h=7): min(8, 7) * 7 = 49

height = [1, 1]  →  1

Note: This is not trapping rain in the valleys. Rain water asks how much sits over every bar, bounded by neighbors. This prompt asks for the largest rectangle two walls can form. Different geometry; do not mix the proofs.

Nested pairs are the honest brute force

Every unordered pair of lines is a candidate. Correct. Quadratic.

int maxAreaNested(int[] height) {
    int best = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = i + 1; j < height.length; j++) {
            int area = Math.min(height[i], height[j]) * (j - i);
            best = Math.max(best, area);
        }
    }
    return best;
}

At n = 20 this is a rounding error. At a year of hourly bars you paid a nested scan for a question two pointers answer in one pass: width shrinks, so move the short wall.

Two pointers from the ends

Start lo at 0 and hi at n - 1. That pair has the maximum possible width. Area is min(height[lo], height[hi]) * (hi - lo). Then you must drop a side.

Width of the next pair is always smaller. The only way area can grow is a taller limiting wall. If you move the taller wall, the new min is at most the short wall you left behind, and the width is worse — that step cannot beat the area you just recorded. Move the shorter wall. Ties: either side; both are limiting.

Walk [1, 8, 6, 2, 5, 4, 8, 3, 7] from the ends:

lo=0 h=1,  hi=8 h=7   area=min(1,7)*8=8     move lo (short)
lo=1 h=8,  hi=8 h=7   area=min(8,7)*7=49    move hi (short)   best=49
lo=1 h=8,  hi=7 h=3   area=min(8,3)*6=18    move hi
lo=1 h=8,  hi=6 h=8   area=min(8,8)*5=40    equal, move lo
lo=2 h=6,  hi=6 h=8   area=min(6,8)*4=24    move lo
lo=3 h=2,  hi=6 h=8   area=min(2,8)*3=6     move lo
lo=4 h=5,  hi=6 h=8   area=min(5,8)*2=10    move lo
lo=5 h=4,  hi=6 h=8   area=min(4,8)*1=4     move lo
lo=6=hi, stop                              best stays 49

The Java is that walk:

int maxArea(int[] height) {
    int lo = 0;
    int hi = height.length - 1;
    int best = 0;
    while (lo < hi) {
        int area = Math.min(height[lo], height[hi]) * (hi - lo);
        best = Math.max(best, area);
        if (height[lo] <= height[hi]) {
            lo++;
        } else {
            hi--;
        }
    }
    return best;
}

Time is O(n) — each index is dropped at most once. Space is O(1) besides the two indexes.

Note: min * width can overflow int if they widen the type. Name that if they switch to long heights. Empty or single-bar input is area 0; the loop never runs.

What interviewers usually poke next

  • Why not move the tall wall? Width shrinks. The leftover short wall still caps the min. Area cannot improve. Say that before they ask you to “try both.”
  • Equal heights. Either pointer. Moving both in one step is also legal; you already counted that width.
  • Trapping rain water (the histogram). Different problem: water over every index, bounded by the tallest bar to the left and right. Do not recycle this two-pointer proof. Stay on this prompt.
  • Overflow / null. Production would reject a null array. At the board, ask.

You are done with this problem when you can say, out loud, why nested pairs are correct, why the width argument forces you to move the short wall, and why this is not the rain-water histogram.