Given n
non-negative integers a1, a2, ..., an
, where each represents a point at coordinate (i, ai)
. n
vertical lines are drawn such that the two endpoints of the line i
is at (i, ai)
and (i, 0)
. Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
-
maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) // should return 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.
-
maxArea([1, 1]) // should return 1
-
maxArea([4, 3, 2, 1, 4]) // should return 16
-
maxArea([1, 2, 1]) // should return 2
- Time Complexity: O(N2)
- Space Complexity: O(1)
/**
* @param {number[]} height
* @return {number}
*/
function maxArea(height) {
// Initialize a variable to track the largest area
let largest = 0;
// Loop over the height array (a)
for (let a = 0; a < height.length; a++) {
// Loop over the succeeding elements (b)
for (let b = a + 1; b < height.length; b++) {
// Using the two current elements,
// calculate the area of the container
//? Area = Length * Width
//? Length = min(height[a], height[b])
//? Width = b - a
const area = Math.min(height[a], height[b]) * (b - a);
// Update the largest area as needed
largest = Math.max(largest, area);
}
}
// Return the largest area
return largest;
}
- Time Complexity: O(N)
- Space Complexity: O(1)
/**
* @param {number[]} height
* @return {number}
*/
function maxArea(height) {
// Initialize two pointers (a and b)
//? a points to start, b points to end
let a = 0;
let b = height.length - 1;
// Initialize a variable to track the largest area
let largest = 0;
// Loop while a is behind b:
while (a < b) {
// Using the two current elements,
// calculate the area of the container
//? Area = Length * Width
//? Length = min(height[a], height[b])
//? Width = b - a
const area = Math.min(height[a], height[b]) * (b - a);
// Update the largest area as needed
largest = Math.max(largest, area);
// If height[a] is less than height[b]:
if (height[a] < height[b]) {
// Move a forward
a++;
}
// Otherwise:
else {
// Move b backward
b--;
}
}
// Return the largest area
return largest;
}