Programming
container-with-most-water
container-with-most-water
You are given an array of positive integer where each integer represents vertical line on a chart.Find two lines which together
with the x-axis forms a container that holds the greatest amount of water.return area of water that holds.
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.
Example 1:
1.does the thickness of lines effects the area? assume take up no space.
2.Do the left and right sides of graph counts as walls?
No,the sides cannot be used to form a container.
3.can we pick two values if one value is higher in the middle ?
yes, the value in middle wont affect the container
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
Testcase
0 1 2 3 4
[7,1,2,3,9] 7*4=28(area= l*w)
min(7,9) =7
4(index)-0=4
now 7*4= 28
[] 0
[7] 0
[6,9,3,4,5,8] 6*5=30
0 1 2 3 4 5 8*4 32
min(6,8)=6
5-0=5
6*5=30
min(9,8)=8
5-1=4
so, 8*4=32
Thinking through logical brute force solution
mark the word greatest amount of water using this word form logic
0 1 2 3 4
[7,1,2,3,9]
area= a*b
index subtraction=ai-bi
min(a,b)-(bi-ai)
0 1 2 3 4
[7,1,2,3,9]
a b
max area=0
min(7,1)=1
b-a=1-0=1
min(7,1)*(1-0)=1
now change max area=1
0 1 2 3 4
[7,1,2,3,9]
a b
max area=0
min(7,3)=3
b-a=3-0=3
min(7,3)*(3-0)=9
now change max area=9
0 1 2 3 4
[7,1,2,3,9]
a b
max area=0
min(7,9)=7
b-a=4-0=4
min(7,9)*(4-0)=28
now change max area=28
0 1 2 3 4
[7,1,2,3,9]
a b
max area=0
min(7,2)=2
b-a=2-0=2
min(7,2)*(2-0)=4
now change max area=4
0 1 2 3 4
[7,1,2,3,9]
a b
max area=0
min(7,2)=2
b-a=2-0=2
min(7,2)*(2-0)=4
now change max area=4
coding out through brute force solution
const get max water container=function(heights){
let maxarea=0
for(let p1=0;p1<height.length;p1++)
{
for(let p2=p1+1;p2<height.length;p2++)
{
const height=min(height[p1],height[p2])
const width=p2-p1;
const area=height*width;
maxarea=math.max(maxarea,area)
}
}
return maxarea;
}
Explanation
[7,1,2,3,9]
height.length=4
height[p1]=7,1,2,3,9 iterating loop value
height[p2]=1,2,3,9 iterating loop value
p1=index value=0,1,2,3,4
p2=index value=1,2,3,4
height=min(height[p1],height[p2])=min(7,1)=1
width=p2-p1;=1-0=1
in java
Java
public int maxArea(int[] height) {
int l = 0;
int r = height.length-1;
int area = (r-l)Math.min(height[l], height[r]);
while(l<r)
{
if(height[l]<=height[r])
{
l++;
}
else
{
r--;
}
int curr = (r-l)(Math.min(height[l], height[r]));
if(curr > area)
{
area = curr;
}
}
return area;
}
Top comments (0)