Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith 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

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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.

Example 2:

Input : [1, 5, 4, 3]
Output : 6
Explanation : 5 and 3 are distance 2 apart. So size of the base = 2. Height of container = min(5, 3) = 3.
So total area = 3 * 2 = 6

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive

One straightforward method is to iterate through the height array, compute the potential volumes combining the current height with all other heights, and then identify the maximum value.

Code

Java
class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int n = height.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Calculate the area for each pair (i, j)
                int area = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, area);
            }
        }
        
        return maxArea;
    }
}
Python
class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area: int = 0
        n: int = len(height)
        
        for i in range(n):
            for j in range(i + 1, n):
                # Calculate the area for each pair (i, j)
                area = min(height[i], height[j]) * (j - i)
                max_area = max(max_area, area)
        
        return max_area

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Two Pointers

The volume of a container is determined by two factors: width and height. By starting from both ends of the array and moving towards the middle, height becomes the limiting factor.

Initially, assume the result is 0 and scan the array from both ends. If the left height is less than the right height, move the left pointer rightwards to find a higher value. Conversely, if the left height is greater than the right height, move the right pointer leftwards to find a higher value. Throughout the process, continually track the maximum value.

Code

Java
class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        
        while (l < r) {
            // Calculate area and update max
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            
            // Move the pointer associated with smaller height
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        
        return ans;
    }
}
Python
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans: int = 0
        
        while l < r:
            # Calculate area and update max
            area = min(height[l], height[r]) * (r - l)
            ans = max(ans, area)
            
            # Move the pointer associated with smaller height
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)