Debug School

rakesh kumar
rakesh kumar

Posted on

Array:Container with most water

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

Image description

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.
Enter fullscreen mode Exit fullscreen mode 
Example 2:

Input: height = [1,1]
Output: 1
Enter fullscreen mode Exit fullscreen mode

Testcase 

 0 1 2 3 4
[7,1,2,3,9]  7*4=28(area= l*w)
Enter fullscreen mode Exit fullscreen mode 
min(7,9) =7
4(index)-0=4
now 7*4= 28
Enter fullscreen mode Exit fullscreen mode 
[]               0
[7]              0
Enter fullscreen mode Exit fullscreen mode 
[6,9,3,4,5,8]           6*5=30
 0 1 2 3 4 5            8*4 32
Enter fullscreen mode Exit fullscreen mode 
min(6,8)=6
5-0=5
6*5=30
Enter fullscreen mode Exit fullscreen mode 
min(9,8)=8
5-1=4
so, 8*4=32
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode 
area= a*b
Enter fullscreen mode Exit fullscreen mode 
index subtraction=ai-bi
Enter fullscreen mode Exit fullscreen mode 
min(a,b)-(bi-ai)
Enter fullscreen mode Exit fullscreen mode 
 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
Enter fullscreen mode Exit fullscreen mode 
 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
Enter fullscreen mode Exit fullscreen mode 
 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
Enter fullscreen mode Exit fullscreen mode 
 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
Enter fullscreen mode Exit fullscreen mode 
 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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)