Container With Most Water

MEDIUM

Description

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.

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: height = [1,1]
Output: 1

Constraints:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

Approaches

Checkout 2 different approaches to solve Container With Most Water. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

The most straightforward solution is to consider every possible pair of vertical lines and calculate the area of the container they form. We can then keep track of the maximum area found among all pairs.

Algorithm

Initialize a variable maxArea to 0.
Use a for loop to iterate from the first line i = 0 to the second to last line n-2.
Inside this loop, use another for loop to iterate from j = i + 1 to the last line n-1.
For each pair of lines (i, j), calculate the area: area = Math.min(height[i], height[j]) * (j - i).
Compare this area with maxArea and update maxArea if the current area is larger: maxArea = Math.max(maxArea, area).
After the loops complete, return maxArea.

This method involves using two nested loops to iterate through all possible pairs of lines. The outer loop selects the first line (i), and the inner loop selects the second line (j), where j is always to the right of i. For each pair (i, j), the area is calculated as the product of the distance between the lines (j - i) and the height of the shorter line (min(height[i], height[j])). We maintain a variable, maxArea, which is updated whenever a larger area is found. After checking all pairs, maxArea will hold the result.

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++) {
                int currentHeight = Math.min(height[i], height[j]);
                int currentWidth = j - i;
                int currentArea = currentHeight * currentWidth;
                maxArea = Math.max(maxArea, currentArea);
            }
        }
        return maxArea;
    }
}

Complexity Analysis

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

Pros and Cons

Pros:

Simple to understand and implement.
Guaranteed to find the correct answer as it checks every possibility.

Cons:

Very inefficient due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for large input sizes.

Code Solutions

Checking out 5 solutions in different languages for Container With Most Water. Click on different languages to view the code.

public class Solution {
    public int MaxArea(int[] height) {
        int i = 0, j = height.Length - 1;
        int ans = 0;
        while (i < j) {
            int t = Math.Min(height[i], height[j]) * (j - i);
            ans = Math.Max(ans, t);
            if (height[i] < height[j]) {
                ++i;
            } else {
                --j;
            }
        }
        return ans;
    }
}

Video Solution

Watch the video walkthrough for Container With Most Water

Patterns:

Two PointersGreedy

Data Structures:

Array

Companies:

Accenture |Accolite |Adobe |Amazon |