Scale Engineer

Container With Most Water

Med
#0011Time: O(n^2)Space: O(1)50 companies
Patterns
Two PointersGreedy
Data structures
Array
Companies
AccentureAccoliteAdobeAmazon

Prompt

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.

 

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 <= 105
  • 0 <= height[i] <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(n^2)

Space

O(1)

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem