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.
1#include <iostream>
2#include <vector>
3
4int maxArea(std::vector<int>& height) {
5 int left = 0, right = height.size() - 1;
6 int max_area = 0;
7 while (left < right) {
8 int h = std::min(height[left], height[right]);
9 max_area = std::max(max_area, h * (right - left));
10 height[left] < height[right] ? left++ : right--;
11 }
12 return max_area;
13}
14
15int main() {
16 std::vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
17 std::cout << "Max area: " << maxArea(height) << std::endl;
18 return 0;
19}The C++ implementation uses a std::vector to store the heights and applies the two-pointer technique in a similar manner to maximize the water container area.
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.
1using System;
2
3public class Solution
4{
5 public int MaxArea(int[] height)
6 {
7 int maxArea = 0;
8 for (int i = 0; i < height.Length - 1; i++)
9 {
10 for (int j = i + 1; j < height.Length; j++)
11 {
12 int h = Math.Min(height[i], height[j]);
13 maxArea = Math.Max(maxArea, h * (j - i));
14 }
15 }
16
17 return maxArea;
18 }
19
20 public static void Main(string[] args)
21 {
22 Solution solution = new Solution();
23 int[] height = {1,8,6,2,5,4,8,3,7};
24 Console.WriteLine("Max area: " + solution.MaxArea(height));
25 }
26}The C# brute force solution uses nested loops to check all possible pairs of lines and computes the container's maximum water area.