Debug School

rakesh kumar

Posted on • Updated on

Array:Trapping with rainwater

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

===========OR=============================
Given an array of integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

``````Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
``````
``````Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
``````

1.Do the left and right sides of graph counts as walls?

No,the sides cannot be used to form a container.

2.will be there negative integer ?

[0,1,0,2,1,0,3,1,0,1,2] 8
[] 0
[3] 0
[3,4,3] 0

Thinking about a logical solution

``````current water = min(maxL,maxR)-cH

total=0

maxL=0
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a
b

total=0

maxL=a=0

maxR=b=0
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a
b

total=0

maxL=a=0

maxR=b=1
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a
b

total=0

maxL=a=0

maxR=b=1
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a

b
total=0

maxL=a=0

maxR=b=2
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a
b
total=0

maxL=a=0

maxR=b=3
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

cH=0

min(maxL,maxR)=(0,3)=0

current water = min(maxL,maxR)-cH= 0-0=0

[0,1,0,2,1,0,3,1,0,1,2]

cH=1
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a
b
total=0

maxL=a=1

maxR=b=1
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a
b
total=0

maxL=a=1

maxR=b=1
``````
``````[0,1,0,2,1,0,3,1,0,1,2]

a          b

total=0

maxL=a=1

maxR=b=3

cH=1

min(maxL,maxR)=(1,3)=1

current water = min(maxL,maxR)-cH= 0-1=-1
``````

ex1)

``````
``````

[0,1,0,2,1,0,3,1,0,1,2]

cH=0(index3)

``````
``````

[0,1,0,2,1,0,3,1,0,1,2]

`````` a
b
``````

total=-1

maxL=a=1

maxR=b=0

``````
``````

[0,1,0,2,1,0,3,1,0,1,2]

a
b
total=-1

maxL=a=1

maxR=b=2

``````
``````

[0,1,0,2,1,0,3,1,0,1,2]

a  b

total=-1

maxL=a=1

maxR=b=2

``````
``````

[0,1,0,2,1,0,3,1,0,1,2]

a

3

total=-1

maxL=a=1

maxR=b=3

min(maxL,maxR)=(1,3)=1

current water = min(maxL,maxR)-cH= 1-1=0

coding out through brute force solution

[0,1,0,2,1,0,3,1,0,1,2]

``````Formulla=min(maxleft,maxright)-ch
``````
``````const get trapped rainwater=function(height){

let total water=0;

for(let let p=0;p<height.length;p++)

{

let leftp=0,rightp=p,maxleft=0,maxright=0;

while(left p>=0)

{

maxleft=Math.max(maxleft,height[leftp]);

leftp--;

}

while(right p<height.length)

{

maxright=Math.max(maxright,height[rightp]);

rightp++;

}

const  currentwater=Math.min(maxleft,maxright)-height[p];

if(currentwater>=0){

total water+=currentwater

}

}

return total water;

}
``````

java

``````public static int trapping_water(int[] height)
{
int total = 0;
for(int i = 0 ; i < height.length ; i++)
{
int max_l = 0;
int max_r = 0;
int l = i;
int r = i;
int curr_height = height[i];
while(r < height.length)
{
if(height[r] > max_r)
{
max_r = height[r];
}
r++;
}
while(l>=0)
{
if(height[l] > max_l)
{
max_l = height[l];
}
l--;
}
int water_level = (Math.min(max_r, max_l) - curr_height);
if(water_level > 0)
{
total = total + water_level;
}
}

return total;
}
``````

Figuring out our optimization strategy

[0,1,0,2,1,0,3,1,0,1,2]

First for outer loop

``````height.length=11
``````
``````while(left p>=0)

{

maxleft=Math.max(maxleft,height[leftp]);

leftp--;

}
``````
``````0>=0
so,maxleft=Math.max(maxleft,height[leftp]); maxleft=Math.max(0,0);=0
leftp--=-1
-1>=0 false so out of loop
``````
``````while(right p<height.length)

{

maxright=Math.max(maxright,height[rightp]);

rightp++;

}
``````
``````right p<height.length=0<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(0,0);=0
``````
``````rightp++=0 to 1

right p<height.length=1<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(0,1);=1
``````
``````rightp++=1 to 2

right p<height.length=2<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(1,0);=1
``````
``````rightp++=2 to 3
right p<height.length=3<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(1,2);=2
``````
``````rightp++=3 to 4
right p<height.length=4<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(2,1);=2
``````
``````rightp++=4 to 5
right p<height.length=5<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(2,0);=2
``````
``````rightp++=5 to 6
right p<height.length=6<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(2,3);=3
``````
``````rightp++=6 to 7
right p<height.length=7<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,1);=3
``````
``````rightp++=7 to 8
right p<height.length=8<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,0);=3
``````
``````rightp++=8 to 9
right p<height.length=9<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,1);=3
``````
``````rightp++=9 to 10
right p<height.length=10<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,2);=3
``````
``````const  currentwater=Math.min(maxleft,maxright)-height[p]);

(Math.min(0,3)-0)=0-0=0
``````
``````if(currentwater>=0){

total water+=currentwater

}
``````
``````total water+=currentwater=0+0=0
return total water=0
``````
``````total water=0
``````

First second outer loop
total=0

``````for(let let p=0;p<height.length;p++)
and p =1
``````
``````height.length=11
``````
``````while(left p>=0)

{

maxleft=Math.max(maxleft,height[leftp]);

leftp--;

}
``````
``````1>=0
so,maxleft=Math.max(maxleft,height[leftp]); maxleft=Math.max(0,1);=1
leftp--=0
0>=0 true next loop
``````
``````0>=0
so,maxleft=Math.max(maxleft,height[leftp]); maxleft=Math.max(0,1);=1
leftp--=-1
-1>=0 false so out of loop
``````
``````while(right p<height.length)

{

maxright=Math.max(maxright,height[rightp]);

rightp++;

}
``````
``````right p<height.length=1<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(0,1);=1
``````
``````rightp++=1 to 2

right p<height.length=2<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(1,0);=1
``````
``````rightp++=2 to 3

right p<height.length=3<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(1,2);=2
``````
``````rightp++=3 to 4
right p<height.length=4<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(2,1);=2
``````
``````rightp++=4 to 5
right p<height.length=5<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(2,0);=2
``````
``````rightp++=5 to 6
right p<height.length=6<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(2,3);=3
``````
``````rightp++=6 to 7
right p<height.length=7<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,1);=3
``````
``````rightp++=7 to 8
right p<height.length=8<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,1);=3
``````
``````rightp++=8 to 9
right p<height.length=9<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,1);=3
``````
``````rightp++=9 to 10
right p<height.length=10<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,2);=3
``````
``````rightp++=10 to 11
right p<height.length=10<11
so,maxright=Math.max(maxright,height[rightp]); maxright=Math.max(3,2);=3
``````
``````const  currentwater=Math.min(maxleft,maxright)-height[p]);

(Math.min(1,3)-0)=0-0=0
``````
``````if(currentwater>=0){

total water+=currentwater

}
``````
``````total water+=currentwater=0+0=0
return total water=0
``````
``````

total water=0
``````