11. Container With Most Water
LeetCode Problems
In this tutorial we will solve 11. Container With Most Water from leetcode.
Table of Content
Reference: 11. Container With Most Water
Problem statement
We are given an input integer array heights of length n and we are asked to find the maximum area between two heights. The input array represents n vertical lines. The coordinate of the ith line is (i, 0) and (i, heights[i]).
Example from leetcode.
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: 1
Constraints:
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
Following is the representation of example 1.
^
|
8 -+ + +
| | |
7 -+ | | +
| | | |
6 -+ | + | |
| | | | |
5 -+ | | + | |
| | | | | |
4 -+ | | | + | |
| | | | | | |
3 -+ | | | | | + |
| | | | | | | |
2 -+ | | + | | | | |
| | | | | | | | |
1 -+ + | | | | | | | |
| | | | | | | | | |
0 -+---+---+---+---+---+---+---+---+---+--->
1 2 3 4 5 6 7 8 9
Max area is between element at position 2 (element 8) and position 9 (element 7).
Minimum height is min(8,7) = 7.
Distance between the two elements = 9-2 = 7
Area = 7 x 7 = 49
^
|
8 -+ + +
| | |
7 -+ |---------------------------+
| |░░░░░░░░░░░░░░░░░░░|░░░░░░░|
6 -+ |░░░+░░░░░░░░░░░░░░░|░░░░░░░|
| |░░░|░░░░░░░░░░░░░░░|░░░░░░░|
5 -+ |░░░|░░░░░░░+░░░░░░░|░░░░░░░|
| |░░░|░░░░░░░|░░░░░░░|░░░░░░░|
4 -+ |░░░|░░░░░░░|░░░+░░░|░░░░░░░|
| |░░░|░░░░░░░|░░░|░░░|░░░░░░░|
3 -+ |░░░|░░░░░░░|░░░|░░░|░░░+░░░|
| |░░░|░░░░░░░|░░░|░░░|░░░|░░░|
2 -+ |░░░|░░░+░░░|░░░|░░░|░░░|░░░|
| |░░░|░░░|░░░|░░░|░░░|░░░|░░░|
1 -+ + |░░░|░░░|░░░|░░░|░░░|░░░|░░░|
| | |░░░|░░░|░░░|░░░|░░░|░░░|░░░|
0 -+---+---+---+---+---+---+---+---+---+--->
1 2 3 4 5 6 7 8 9
Approach
To solve this problem we will use two pointers. We start by setting the left pointer pointing at the first element and the right pointer pointing at the last element. In each iteration we will check which is the smallest height, left element or the right element and the distance between them. We compute the area between left and right element. If the area is a new larger area then we update our max area. In the end of each loop we check if the height of the left element is smaller than the right element. If it is then we increment left pointer by 1. On the other hand, we decrement the right pointer by 1.
Let us solve the first input height = [1,8,6,2,5,4,8,3,7]
area = 0
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(1, 7) = 1
-> distance = 8 - 0 = 8
-> area = max(area, minHeight * distance)
= max(0, 1*8)
= max(0, 8)
= 8
-> is height[l] < height[r] ?
-> i.e., is 1 < 7 ? yes
-> increment l by 1
-> new l = 1
area = 8
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(8, 7) = 7
-> distance = 8 - 1 = 7
-> area = max(area, minHeight * distance)
= max(8, 7*7)
= max(8, 49)
= 49
-> is height[l] < height[r] ?
-> i.e., is 8 < 7 ? no
-> decrement r by 1
-> new r = 7
area = 49
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(8, 3) = 3
-> distance = 7 - 1 = 6
-> area = max(area, minHeight * distance)
= max(49, 3*6)
= max(49, 18)
= 49
-> is height[l] < height[r] ?
-> i.e., is 8 < 3 ? no
-> decrement r by 1
-> new r = 6
area = 49
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(8, 8) = 8
-> distance = 6 - 1 = 5
-> area = max(area, minHeight * distance)
= max(49, 8*5)
= max(49, 40)
= 49
-> is height[l] < height[r] ?
-> i.e., is 8 < 8 ? no
-> decrement r by 1
-> new r = 5
area = 49
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(8, 4) = 4
-> distance = 5 - 1 = 4
-> area = max(area, minHeight * distance)
= max(49, 4*4)
= max(49, 16)
= 49
-> is height[l] < height[r] ?
-> i.e., is 8 < 4 ? no
-> decrement r by 1
-> new r = 4
area = 49
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(8, 5) = 5
-> distance = 4 - 1 = 3
-> area = max(area, minHeight * distance)
= max(49, 5*3)
= max(49, 15)
= 49
-> is height[l] < height[r] ?
-> i.e., is 8 < 5 ? no
-> decrement r by 1
-> new r = 3
area = 49
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(8, 2) = 2
-> distance = 3 - 1 = 2
-> area = max(area, minHeight * distance)
= max(49, 2*2)
= max(49, 4)
= 49
-> is height[l] < height[r] ?
-> i.e., is 8 < 2 ? no
-> decrement r by 1
-> new r = 2
area = 49
index = 0 1 2 3 4 5 6 7 8
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
l r
is l < r ? yes
-> minHeight = min(8, 6) = 6
-> distance = 2 - 1 = 1
-> area = max(area, minHeight * distance)
= max(49, 6*1)
= max(49, 6)
= 49
-> is height[l] < height[r] ?
-> i.e., is 8 < 6 ? no
-> decrement r by 1
-> new r = 1
is l < r ? no
so we stop here
Code
JavaScript
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let area = 0;
let l = 0;
let r = height.length - 1;
while (l < r) {
const minHeight = Math.min(height[l], height[r]);
const len = r - l;
area = Math.max(area, minHeight * len);
if (height[l] < height[r]) l++;
else r--;
}
return area;
};Complexity
Time complexity: O(n)
For an input array of n elements the loop will run n-1 times so the time complexity will be O(n).
Space complexity: O(1)
To solve this problem we are using only constant space so space complexity is O(1).
ADVERTISEMENT