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 <stdio.h>
2
3int maxArea(int* height, int heightSize) {
4 int left = 0, right = heightSize - 1;
5 int max_area = 0;
6 while (left < right) {
7 int h = height[left] < height[right] ? height[left] : height[right];
8 int current_area = h * (right - left);
9 if (current_area > max_area) max_area = current_area;
10
11 if (height[left] < height[right]) left++;
12 else right--;
13 }
14 return max_area;
15}
16
17int main() {
18 int height[] = {1,8,6,2,5,4,8,3,7};
19 int result = maxArea(height, sizeof(height) / sizeof(height[0]));
20 printf("Max area: %d\n", result);
21 return 0;
22}This C implementation defines a function maxArea which takes an array of heights and iteratively calculates the maximum water that can be contained using a two-pointer approach. The output is printed after calling the function.
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.
1#include <iostream>
2#include <vector>
3
4int maxArea(std::vector<int>& height) {
5 int max_area = 0;
6 for (size_t i = 0; i < height.size() - 1; ++i) {
7 for (size_t j = i + 1; j < height.size(); ++j) {
8 int h = std::min(height[i], height[j]);
9 max_area = std::max(max_area, h * (j - i));
10 }
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 iterates over every possible pair of heights, calculating the potential water area for each pair to find the maximum.