The two pointers approach efficiently searches for the maximum area by starting with the widest possible container and gradually narrowing it:
This approach works due to the observation that the area is limited by the shorter line, so the only way to get a larger area is to find a taller line.
Time Complexity: O(n), where n is the number of elements in the height array, due to the single traversal of the array.
Space Complexity: O(1) as only a few extra variables are used.
1using System;
2
3public class Solution
4{
5 public int MaxArea(int[] height)
6 {
7 int left = 0, right = height.Length - 1;
8 int maxArea = 0;
9
10 while (left < right)
11 {
12 int h = Math.Min(height[left], height[right]);
13 maxArea = Math.Max(maxArea, h * (right - left));
14
15 if (height[left] < height[right])
16 {
17 left++;
18 }
19 else
20 {
21 right--;
22 }
23 }
24
25 return maxArea;
26 }
27
28 public static void Main(string[] args)
29 {
30 Solution solution = new Solution();
31 int[] height = {1,8,6,2,5,4,8,3,7};
32 Console.WriteLine("Max area: " + solution.MaxArea(height));
33 }
34}This C# solution uses two pointers to dynamically calculate the water container's maximum area, updating it whenever a larger area is found and moving the pointers based on the shorter height.
Although not optimal for large inputs, the brute force approach explores every possible pair of lines to find the maximum container area:
However, the complexity of this approach makes it unsuitable for large datasets due to its quadratic time complexity.
Time Complexity: O(n^2), where n is the number of elements as each pair is checked.
Space Complexity: O(1) due to a linear amount of extra space.
1public class Solution {
2 public int maxArea(int[] height) {
3 int maxArea = 0;
4 for (int i = 0; i < height.length - 1; i++) {
5 for (int j = i + 1; j < height.length; j++) {
6 int h = Math.min(height[i], height[j]);
7 maxArea = Math.max(maxArea, h * (j - i));
8 }
9 }
10 return maxArea;
11 }
12
13 public static void main(String[] args) {
14 Solution solution = new Solution();
15 int[] height = {1,8,6,2,5,4,8,3,7};
16 System.out.println("Max area: " + solution.maxArea(height));
17 }
18}This Java solution checks every possible pair of lines to calculate the max water container area using nested loops.