Container With Most Water

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Two pointers from both ends. Area = min(height[l], height[r]) * (r-l). Move the shorter side inward.

Algorithm

1l=0, r=n-1. max_area=0.
2While l<r: area = min(height[l],height[r])*(r-l). max_area = max. Move shorter side.

Common Pitfalls

•Moving shorter side can only increase area. Moving taller side can only decrease width without gain.

Container With Most Water.java

Java

// Approach: Two pointers starting at both ends. Move the pointer with the shorter height inward.
// Track the maximum area computed at each step.
// Time: O(n) Space: O(1)
class Solution {

    public int maxWater(int arr[]) {
        int n = arr.length;
        int s = 0;
        int e = n - 1;
        int m = 0;

        while (s <= e) {
            int w = e - s;
            int h = Math.min(arr[s], arr[e]);
            m = Math.max(m, w * h);

            if (arr[s] < arr[e])
                s++;
            else
                e--;
        }
        
        return m;
    }
}

Was this solution helpful?