thesarfo

Reference

Container With Most Water

Finding the two bars that hold the most water using brute force vs. two pointers that always move the shorter bar.

views 0

Given bar heights, find two bars that (with the x-axis) form the container holding the most water. (LeetCode problem) Water between bars i and j is (j - i) * min(height[i], height[j]).

Brute force: every pair of bars — O(n²).

class Solution {
    public int maxArea(int[] height) {
        int maxWater = 0;


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


        return maxWater;
    }
}

Optimal — two pointers from both ends: start at the widest possible container (i=0, j=n-1), and always move the pointer at the shorter bar inward — that’s the only move that could possibly find a taller bar and improve the result, since width only shrinks from here.

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int maxWater = 0;


        while (i < j) {
            int water = (j - i) * Math.min(height[i], height[j]);
            maxWater = Math.max(maxWater, water);


            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }


        return maxWater;
    }
}

For height = [1,4,2,3]: i=0,j=3 → water 3, move i (shorter); i=1,j=3 → water 6 (new max), move j; i=1,j=2 → water 2. Stop when i==j. Result: 6.

Time: O(n), single pass. Space: O(1).