Debug School

rakesh kumar
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:
Image description

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

Input: height = [4,2,0,3,2,5]
Output: 9
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode 
[0,1,0,2,1,0,3,1,0,1,2]

 a
 b

 total=0

maxL=a=0

maxR=b=0
Enter fullscreen mode Exit fullscreen mode 
[0,1,0,2,1,0,3,1,0,1,2]

 a
   b

 total=0

maxL=a=0

maxR=b=1
Enter fullscreen mode Exit fullscreen mode 
[0,1,0,2,1,0,3,1,0,1,2]

 a    
     b

 total=0

maxL=a=0

maxR=b=1
Enter fullscreen mode Exit fullscreen mode 
[0,1,0,2,1,0,3,1,0,1,2]

 a       

       b
 total=0

maxL=a=0

maxR=b=2
Enter fullscreen mode Exit fullscreen mode 
[0,1,0,2,1,0,3,1,0,1,2]

 a                 
             b
 total=0

maxL=a=0

maxR=b=3
Enter fullscreen mode Exit fullscreen mode 
[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
Enter fullscreen mode Exit fullscreen mode 
[0,1,0,2,1,0,3,1,0,1,2]

   a 
   b
 total=0

maxL=a=1

maxR=b=1
Enter fullscreen mode Exit fullscreen mode 
[0,1,0,2,1,0,3,1,0,1,2]

   a       
     b
 total=0

maxL=a=1

maxR=b=1
Enter fullscreen mode Exit fullscreen mode 
[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
Enter fullscreen mode Exit fullscreen mode

ex1)
Enter fullscreen mode Exit fullscreen mode

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

cH=0(index3)
Enter fullscreen mode Exit fullscreen mode

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

 a
 b
Enter fullscreen mode Exit fullscreen mode

total=-1

maxL=a=1

maxR=b=0
Enter fullscreen mode Exit fullscreen mode

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

    a 
b
total=-1

maxL=a=1

maxR=b=2
Enter fullscreen mode Exit fullscreen mode

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

    a  b

total=-1

maxL=a=1

maxR=b=2
Enter fullscreen mode Exit fullscreen mode

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

}
Enter fullscreen mode Exit fullscreen mode

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

Figuring out our optimization strategy

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

First for outer loop

height.length=11
Enter fullscreen mode Exit fullscreen mode 
while(left p>=0)

{

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

leftp--;

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

{

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

rightp++;

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


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

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

(Math.min(0,3)-0)=0-0=0
Enter fullscreen mode Exit fullscreen mode 
if(currentwater>=0){

total water+=currentwater

}
Enter fullscreen mode Exit fullscreen mode 
total water+=currentwater=0+0=0
return total water=0
Enter fullscreen mode Exit fullscreen mode 
total water=0
Enter fullscreen mode Exit fullscreen mode

First second outer loop
total=0

for(let let p=0;p<height.length;p++)
and p =1
Enter fullscreen mode Exit fullscreen mode 
height.length=11
Enter fullscreen mode Exit fullscreen mode 
while(left p>=0)

{

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

leftp--;

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

{

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

rightp++;

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


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

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

(Math.min(1,3)-0)=0-0=0
Enter fullscreen mode Exit fullscreen mode 
if(currentwater>=0){

total water+=currentwater

}
Enter fullscreen mode Exit fullscreen mode 
total water+=currentwater=0+0=0
return total water=0
Enter fullscreen mode Exit fullscreen mode 


total water=0
Enter fullscreen mode Exit fullscreen mode

Top comments (0)