Leetcode – 11. Container With Most Water
Problem
Solution
Idea
My idea is straightforward using brute force technique.
– Loop through the array of heights
– Another loop through the array from the end
– Calculate the area and get the maxArea
At the first run, I’ve got Time Exceeds error (of course), so I add a condition to break the inner loop.
// start * distance is the maximum area the start can achieve
// if it's already smaller than the maxArea, we don't need to calculate anymore
if (maxArea > (start * distance)) {
break;
}Yes it works although the result is not great. My solution is too slow.
You can read the optimize solution here: 11. Container With Most Water – LeetCode Fastest Solution. It uses the two pointer technique. The result is great.
Code
Brute force
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxArea = 0;
for (let i = 0; i < height.length - 1; i++) {
let start = height[i];
for (let j = height.length - 1; j > i; j--) {
let h = height[j] >= start ? start : height[j];
let distance = j - i;
let area = h * distance;
if (area > maxArea) {
maxArea = area;
}
// start * distance is the maximum area the start can achieve
// if it's already smaller than the maxArea, we don't need to calculate anymore
if (maxArea > (start * distance)) {
break;
}
}
}
return maxArea;
};Optimize solution from code recipe:
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let n = height.length;
let left = 0;
let right = n - 1;
let result = 0;
while(left < right) {
let currentResult = Math.min(height[left], height[right]) * (right - left);
result = Math.max(result, currentResult);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return result;
};