Skip to content
AI360Xpert
Back to Two Pointers
Medium

Container With Most Water

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `i`th line are `(i, 0)` and `(i, height[i])`. Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.

Examples

Input:height = [1,8,6,2,5,4,8,3,7]
Output:49
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49 (between lines at index 1 and 8, height is 7, width is 7).

Constraints

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

Approach

Iterate through every possible pair of lines using two nested loops. For each pair, calculate the area as `min(height[left], height[right]) * (right - left)`. Keep track of the maximum area found.

Complexity Analysis

Time Complexity
O(n^2)
Space Complexity
O(1)

This approach will result in a Time Limit Exceeded (TLE) error for large input arrays.

Solution.java
class Solution {    public int maxArea(int[] height) {        int maxArea = 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);                maxArea = Math.max(maxArea, area);            }        }                return maxArea;    }}