Description:
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.
Examples:
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: 1Solution in Python:
To solve the problem of finding the maximum area of water a container can hold using two lines from the given height array, we can use the two-pointer approach. This approach is efficient and runs in O(n) time complexity.
Python
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
# Initialize two pointers
left = 0
right = len(height) - 1
# Variable to store the maximum area found
max_area = 0
# Loop until the two pointers meet
while left < right:
# Calculate the width between the two pointers
width = right - left
# Calculate the area formed between the lines at the two pointers
current_area = min(height[left], height[right]) * width
# Update the maximum area if the current area is larger
max_area = max(max_area, current_area)
# Move the pointer pointing to the shorter line inward
if height[left] < height[right]:
left += 1
else:
right -= 1
# Return the maximum area found
return max_area
# Example usage:
sol = Solution()
print(sol.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])) # Output: 49
print(sol.maxArea([1, 1])) # Output: 1Explanation:
- Initialization: We initialize
leftto the start of the array andrightto the end.max_areais initialized to 0 to keep track of the maximum area found. - Main Loop: We iterate while
leftis less thanright.- Width Calculation: The width between the two pointers is
right - left. - Area Calculation: The current area is the minimum height of the two lines multiplied by the width.
- Update Maximum Area: We update
max_areaif the current area is greater than the previously storedmax_area. - Move Pointers: We move the pointer pointing to the shorter line inward because moving the pointer of the taller line won’t increase the height, but moving the shorter one might.
- Width Calculation: The width between the two pointers is
- Return Result: Finally, we return the
max_areawhich holds the maximum area of water that can be contained.
This solution is efficient and handles the constraints well, providing an optimal solution to the problem.
Solution in Javascript:
JavaScript
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
// Initialize two pointers
let left = 0;
let right = height.length - 1;
// Variable to store the maximum area found
let maxArea = 0;
// Loop until the two pointers meet
while (left < right) {
// Calculate the width between the two pointers
let width = right - left;
// Calculate the area formed between the lines at the two pointers
let currentArea = Math.min(height[left], height[right]) * width;
// Update the maximum area if the current area is larger
maxArea = Math.max(maxArea, currentArea);
// Move the pointer pointing to the shorter line inward
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
// Return the maximum area found
return maxArea;
};
// Example usage:
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // Output: 49
console.log(maxArea([1, 1])); // Output: 1Solution in Java:
Java
class Solution {
public int maxArea(int[] height) {
// Initialize two pointers
int left = 0;
int right = height.length - 1;
// Variable to store the maximum area found
int maxArea = 0;
// Loop until the two pointers meet
while (left < right) {
// Calculate the width between the two pointers
int width = right - left;
// Calculate the area formed between the lines at the two pointers
int currentArea = Math.min(height[left], height[right]) * width;
// Update the maximum area if the current area is larger
maxArea = Math.max(maxArea, currentArea);
// Move the pointer pointing to the shorter line inward
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
// Return the maximum area found
return maxArea;
}
// Example usage
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // Output: 49
System.out.println(sol.maxArea(new int[]{1, 1})); // Output: 1
}
}Solution in C#:
C#
public class Solution {
public int MaxArea(int[] height) {
// Initialize two pointers
int left = 0;
int right = height.Length - 1;
// Variable to store the maximum area found
int maxArea = 0;
// Loop until the two pointers meet
while (left < right) {
// Calculate the width between the two pointers
int width = right - left;
// Calculate the area formed between the lines at the two pointers
int currentArea = Math.Min(height[left], height[right]) * width;
// Update the maximum area if the current area is larger
maxArea = Math.Max(maxArea, currentArea);
// Move the pointer pointing to the shorter line inward
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
// Return the maximum area found
return maxArea;
}
}