🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem involves finding two vertical lines in an array that, together with the x-axis, form a container capable of holding the maximum amount of water. The height of the water container is determined by the shorter of the two lines, and the width is the distance between them. By leveraging the properties of the array and the two-pointer technique, we can efficiently find the optimal solution without needing to check all possible pairs.
Approach
- Two-Pointer Technique:
Initialize two pointers,
left
at the beginning of the array andright
at the end. - Calculate Area:
Compute the area formed by the lines at the
left
andright
pointers, using the formula: \[ \text{area} = (\text{right} - \text{left}) \times \min(\text{height[left]}, \text{height[right]}) \] - Update Maximum Area: Keep track of the maximum area encountered during the iteration.
- Move Pointers:
Adjust the pointers to potentially find a larger area:
- If the height at the
left
pointer is less than the height at theright
pointer, increment theleft
pointer. - Otherwise, decrement theright
pointer. - Terminate:
Repeat steps 2-4 until the
left
pointer is no longer less than theright
pointer. - Return Result: The maximum area found during the iteration is the answer.
Complexity
Time Complexity:
O(n), where n
is the length of the array. Each element is processed at most once by the two pointers.
Space Complexity:
O(1), as the solution only uses a constant amount of extra space for the two pointers and variables.
Code
C++
#include
#include
using namespace std;
class Solution {
public:
int maxArea(vector& height) {
int left = 0;
int right = height.size() - 1;
int maxArea = 0; // Initialize maxArea to 0 instead of -Infinity
while (left < right) {
int area = (right - left) * min(height[left], height[right]);
maxArea = max(maxArea, area);
if (height[left] < height[right]) {
++left;
} else {
--right;
}}
return maxArea;
}};
Python
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = (right - left) * min(height[left], height[right])
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
Java
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0; // Initialize maxArea to 0
while (left < right) {
int area = (right - left) * Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}}
return maxArea;
}}
JavaScript
var maxArea = function(heights) {
let left=0;
let right=heights.length-1
let maxArea=-Infinity
while(left