Repository navigation
LC 011. Container with the most water (Medium)
- https://leetcode.com/problems/container-with-most-water/
- Two Pointers, DP
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.
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 the container can contain is 49.
Input: height = [1,1] Output: 1
Input: height = [1,2,1] Output: 2
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
After being stuck for a long time I looked up at the forums and found this post:
- The widest container (using first and last line) is a good candidate, because of its width. Its water level is the height of the smaller one of first and last line.
- All other containers are less wide and thus would need a higher water level in order to hold more water.
- The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further consideration.
class Solution:
def maxArea(self, height):
i, j = 0, len(height) - 1
water = 0
while i < j:
water = max(water, (j - i) * min(height[i], height[j]))
if height[i] < height[j]:
i += 1
else:
j -= 1
return waterFrom another thread:
"Bucket theory: how much water a bucket can contain depends on the shortest plank. So, as to find the next potential maximum area, we disregard the shorter end by moving it to the next position."
- Using
max()to assign water = max(water, new_value); faster is:if best < current: best = current - Using
min()and also usingif height[i] < height[j]this can be combined. - The while statement is always doing the same amount of iterations. This should be a for loop
Runtime: 616 ms, faster than 97.72% of Python3 online submissions
class Solution:
def maxArea(self, height):
left, right = 0, len(height) - 1
best = curr = 0
for _ in range(len(height)):
if height[left] < height[right]:
curr = (right - left) * height[left]
left += 1
else:
curr = (right - left) * height[right]
right -= 1
if best < curr: best = curr
return bestRuntime: 72 ms, faster than 99.62%
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let length = height.length
let left = 0
let right = length - 1
let best = 0
let curr = 0
for (let i=0; i < length; i++) {
if (height[left] < height[right]) {
curr = (right - left) * height[left++]
} else {
curr = (right - left) * height[right--]
}
if (best < curr) best = curr
}
return best
};36 ms: runtime beats 99.98 % of cpp submissions.
class Solution {
public:
int maxArea(vector<int>& height)
{
// leetcode specific hack
ios::sync_with_stdio(false);
cin.tie(NULL);
int left = 0;
int N = height.size();
int right = N-1;
int best_area = 0;
int curr_area = 0;
for (int i=0; i < N; i++)
{
if(height[left] < height[right]) {
curr_area = (right - left) * height[left++];
} else {
curr_area = (right - left) * height[right--];
}
if (best_area < curr_area) best_area = curr_area;
}
return best_area;
}
};