9 Rain Water Trapping

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Input: arr[] = {2, 0, 2}
Output: 2
Structure is like below
| |
|_|
We can trap 2 units of water in the middle gap.
Input: arr[] = {3, 0, 0, 2, 0, 4}
Output: 10
Structure is like below
|
| |
| | |
|__|_|
We can trap "3*2 units" of water between 3 an 2,
"1 unit" on top of bar 2 and "3 units" between 2
and 4. See below diagram also.
Refer : www.geeksforge... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻‍💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻‍♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.

[@punee673]

This video i watched a year ago definitely got me my job now in my final year. You taught so well i was able to recollect every approach from this. So thanks a ton.

[@subhajitdutta5216]

Great explanation, and u r right jenny mam is pretty😂

[@TheAdityaVerma]

right? You feel me ? !! 😂😂😂😂😂😂😂😂😂😂😂

[@subhajitdutta5216]

@@TheAdityaVerma yup😂🙏, waiting for ur videos though

[@vivektyson]

@@TheAdityaVerma awaaz bhi unka kitna pyaara hai

[@satishchandra2652]

​@@TheAdityaVerma hahhah

[@LetszGoo]

haha she is theory teacher. whenever i see her video i thought seh never coded in her whole life.

[@amanagarwal2022]

Jenny kafi achchha padati hai +sunder bhi dikhti hai! Koi kinta bhi achcha DSA karle aakhir meh rehata engineer he hai 😂😂

[@snverma5357]

men will be men...sargam lolol

[@Shourya_performs]

😂😂

[@deepakffyt2844]

Exam me pass hone ke liye jada tar padhte hai

[@joichirogaming]

The best part of his videos is: he explains from starting tells all expected approaches and their disadvantages and finally tells approach that will give the correct answer and then gives the solution. Hats off!!!!

[@srajikagupta3627]

Volume is very low sir please try to keep it a little more 😅

[@varungupta420]

bhaii boats ke headphones se hi sunai de rha merko

[@abhishekbhowmick5912]

Thanks for this comment, else I would consider this class as mute!

[@devashishbawa8236]

15:50 we understand the double meaning laughter 😂😂😂

[@vagabondfoodie5788]

😂😂😂😂😂.... Are are sir 😭😭😭😂😂😂

[@VishalSinghrajput-hb2sn]

kaise pani nikal na hai

[@ce038_divanshsingh3]

jenny ka pani

[@dsa9980]

Aadi bhai you rock yarr.. !! Bhai aapka teaching style todd hai.. ek baar dekhte hi sab samaz aata hai.. bahot dua lagne wali hai aapko sabki.. You doing a commendable job..!! Hats off yarr..!! I hated DS Algo kyunki mujhe bahot tough lagta tha ye sab.. pr ab nahi.. sala kash kisine aisa angle dikhaya hota pehle.. I love solving problems now and successfully able to find patterns in it. Thanks, man..!! Keep up the good work..!! Waiting for more..!! God bless.. :-)

[@TheAdityaVerma]

Thanks brother !! Such long comments always put a smile across my face ❤️✌️✌️ Also Do share the content amomg your friends and collage to help the channel grow !! Thanks for watching again !!

[@dsa9980]

@@TheAdityaVerma Needless to say.. already shared and received a lot of praise for sharing..!! :D :P

[@TheAdityaVerma]

Thanks a ton !!

[@AbhineetDeep]

@@TheAdityaVerma bro thoda jor se bola kr pls..

[@harishgupta8351]

Man, Teacher's day never made sense to me before but now after watching these videos, my thinking has changed completely. If teachers in India can focus on developing the thought process in students rather than just completing the syllabus and getting their students in merit list, a lot can change in the country.

[@varungoel6981]

Today I got selected in Flipkart all because of your videos Aditya! Besides learning technical stuff, I got to learn from you on how to handle and approach complex problems. Thanks a lot! I really owe you a lot, can't msg on LinkedIn since you haven't accepted my request but I'm gonna ping you as soon as I join to thank you :)

[@crajeducation6733]

apna LinkedIn ka profile do to

[@musclefitnesstv6550]

@@crajeducation6733 😂😂

[@adi5962]

​@@crajeducation6733nhi laga lagta hai

[@vaishnavimovva5048]

Aditya sir is in flipkart too. Hope you get to meet him

[@sankalparora9261]

Great video. Damn amazing. You can't imagine what great service you are delivering. I get the idea and I even figure out the whole code in between the video. This is the sign of a great teacher. He just need to give a sign to the student, and the rest becomes a story. You gave me the true picture of what is APPROACH. Otherwise, I was just understanding the idea of the problem or just memorizing how to solve it. You are a CODING GOD.

[@shubhamthind8286]

You are right 😁

[@luckshay-l6f]

Bro how can i use pair in java ?? Actually I am in doubt

[@anshmishra3066]

2:12 "dekhna hai to jaaker JENNY k lecture dekho dikhti bhi sundar hai aur acha bhi padhati hai" Has a separate fanbase in my college

[@sadhinoor5114]

Bro i really wish i found out about u sooner currently 6th sem passed and watching ur videos for recap......best teacher by far! Mad respect bhaiya!:))

[@akashsrivastava9674]

Where did you get placed?

[@harshkushwaha2212]

Sir, you said you would add the remaining videos later in the playlist. So can you please add them? They are really helping us. Thanks a lot.

[@AniketSinha291]

Very good approach Of breaking down water level at each building level. Minor enhancement: the last loop just to calculate sum can be eliminated. You can instead keep adding to sum right after you calculate water level at index i. sum += water[i]; // after calculating water[i]

[@aniketpathak2721]

bhai ye toh stack ka sawal tha hi nhi

[@aloksingh4110]

Aditya sir ke aagey mahaanta dikhaaega neech aadmi, jaa jaake ppap dho ganga mein

[@anime4u766]

Bhaiya on fire....jenny sundar b lagti h

[@himanshugusain9022]

sir please complete the series , it is much needed. Hats off to your explanation ! if possible add queue playlist also

[@poonamchauhan1884]

Commendable work of finding patterns and categorising problems. When will you be adding the last four problems of the list you shared in the beginning of the playlist?

[@Shourya_performs]

waitingggggg

[@amanjyotiparida5818]

15:52 that 😈 smile...😁😁😁

[@049_neeraj4]

Explanation was really amazing, but where did we use stack.

[@srinivaschaitanya3305]

kaafi achi padathi hai aur sundar bhi dikthi hai..😂😂

[@PrinceKumar-el7ob]

leetcode solution for reference - for noobies like me !! int trap(vector& arr) { int n =arr.size(); vector right_max(n); vector left_max(n); // no matter what we can't store water on edge buildings left_max[0]=arr[0]; for(int i=1;i=0;i--){ right_max[i]=max(arr[i],right_max[i+1]); } int sum=0; for(int i=1;i

[@kirtikhohal3313]

Thanks

[@shashankbhatgs1150]

in case someone needs a java solution: class Solution { public int trap(int[] height) { int n = height.length; int[] maxL = new int[n]; int[] maxR = new int[n]; maxL[0] = height[0]; for(int i = 1; i < n; i++){ maxL[i] = Math.max(maxL[i-1], height[i]); } maxR[n-1] = height[n-1]; for(int i = n-2; i >= 0; i--){ maxR[i] = Math.max(maxR[i+1], height[i]); } int[] water = new int[n]; for(int i = 0; i

[@mfaraday4044]

bhai jitni tarif karu utni kam hai kya content share karte ho aap , ye channel god ka gift hai mere liye aur Aditya verma ( vishnu avatar hai mere life ke liye )

[@TheAdityaVerma]

Arreyy ni bhai, kaha Vishnuji aur kaha me 😅 Michael Faraday kese bnna hai bs wo bta do 😂✌️ jokes apart, Thanks for such a beautiful comment, Love you brother 😅✌️

[@jaineshkumar794]

👏 Never thought DSA could be so much interesting and easy to learn. These aren't easy problems but hats off to you, after seeing your explanation it's a piece of cake ✌

[@logicoverflow1240]

Bhaiya mooj kara di 🔥🔥🔥 maza aagaya

[@SushilKumar-es9ib]

Nobody can explain like you. Your explanations makes hardest problem to the easiest problem. Thanks for that

[@ShubhamKumar-lb9lf]

15:52😅😂

[@TheAdityaVerma]

🙊🙊😂😂

[@AbhijeetKumar-tm5pk]

😂

[@i-am-mkv]

"Apne ko kya hai, apne ko toh bas paani nikaalna hai" 🤣

[@priyanshsaxena2550]

amazing!....jenny ahhhh kyaa baat

[@anupamdubey5736]

Thanks a lot for the awesome explanation. I was able to code only by listening to the explanation without seeing the solution. Please keep this channel organic with such content unlike others who at a later stage adulterate their channel with ads and shortcut videos.

[@baibhavagrawal3441]

Sir i am being your big fan saala puri duniya patani lakhon kharch karke lecture video suit kar raha he aur bhai apna ek page aur mobile phone se unn sabki le raha he.. God Bless bhai.. Love you..

[@Manojrohtela]

Great explanation and Jenny sundar bhi dikhti h savage 😂😂😂😂 Was confuse with this example 1,0,2,0,1,3,1

[@Gauravkr0071]

aditya bhai, tum ho to sb h, vrna kch bhi nhi. dil se dhanyawaad

[@adityagore2147]

2:10 had me going 😂😂😂

[@praveenchouhan6388]

you nailed it!!! I liked the way you have broken the problem down and the concept of maxleft and maxright, awesome, thanks a lot!!!

[@deepakdhakad8539]

2:10 yaha boss bhi pighal gye 😂

[@tanmayjain1584]

Yaar mera to dhyaan bhatak jaata hai ...beech beech may pause kar k bs dil pe haath rakh k hsate rehta hun......kitniiii ppyaari hai ye.... lekin han bahot achcha pdhati hai jenny mam

[@kusumjoshi8140]

fuck off.. Aditya Verma is best

[@sauravdas7591]

Good Explanation Programming Lord! But Bro, please create the remaining ones in the list, really appreciate your hard work for explaining the concepts. I wished my DSA teacher be like you.

[@jiteshkumar3112]

brother please complete the series by uploading 4 more questions that you gave in your 1 video of stack

[@lifeexplorer2965]

2:13😂😂

[@TheAdityaVerma]

😅

[@shiwansbhatt1803]

Bahut sundar😂

[@AbhishekSharma-ip4df]

15:51 his laugh after "tho hame samajh a gaya ki hm kaise paani nikal skte h" Ture engineers😂😂 🙌

[@ananya_gupta2328]

"Vo accha pdhati hai, sundar bhi dikhti hai" was heart touching🤣🤣

[@ayushagarwal2032]

when are you releasing backtracking playlist?

[@KartikeyTT]

It took him 3 years

[@babithakumari5884]

can't thankyou enough for these videos, I can't believe I am able to code faster only by understanding the approach.

[@iamvishalaggarwal]

best explanation 🥳

[@youcantgetme1126]

15:45 so , apne ko smj aa gya ki kese Pani nikal skte h ..😂😂 anyone noticed that he laughed at that moment 😅😅

[@mohamedfaizan3095]

2:14 bhaiya op😂😂

[@abhineetsingh6720]

"jenny kafi acha padhati hai aur sundar bhi dikhti hai"

[@vishalkumarshaw9208]

you are OP aditya Bhai...jenny wala dialouge

[@_AmbujJaiswal]

jenny achha padhati h aur sundar bhi dikhti h🤣🤣🤣🤣

[@ajaybhagchandani3307]

This video helped me in solving the leetcode question of Rain water trapping. Thanks alot!

[@aloksingh8851]

I have a doubt here, we didn't use Stacks at all in this solution. I see a stack solution on GFG as well but I can't grasp that, can you please add an explanation for that as well?

[@shyamkachhadiya4964]

wow great problem, solved excellents, there's little maths involved but yea great explanation.

[@CodeKickstart123]

What an explanation 😊

[@Missing_man]

2:10 comment on jenny was awesome 😎😎😂😂😂😂😂😂😂😂

[@teen350]

Suberb explanation😊

[@dheerajpoonia2175]

awesome sir, koi word nhi hai apki tarrif krna ka bss jaab selection honne ke baad sweet lekr faculty k pass too pta nhi jaoga ya nhi but appke pass jurur aaoga :-)

[@Rajjain_]

sunder bhi dikhti hai who😂, But you are the best!

[@deepakffyt2844]

Bhai appse aacha koi nahi padtha KZbin pe ♥️

[@anmolsingh3482]

Great explanation Sir!

[@ArpitKumar-yo6up]

I love your explanation sir

[@nishantingle1438]

There is O(1) space complexity solution to it. This is indeed related to NGL just nearest is changed to farthest. In fact there is no need of stack in NGL, you can just use the same technique to compare with ngl(previous).

[@anonymous090]

how we can solve it in O(1) ??

[@kirtikhohal3313]

I don't think we can say this as farthest greater to left: suppose this is the array: 6 8 0 0 5 9 6 for element=5 max in the left array is 8 max in the right array is 9 min of both is 8 water accumulated on element =5 is 8-5=3. which is correct. But, farthest greater to left is 6 farthest greater to right is 9 min is 6 water accumulated is 6-5 =1, which is wrong

[@lakshkumrawat140]

15:48 kese pani nikal sakte he , and that laughter explains all 😂😂

[@MasoomSahu-q4z]

And jenny sundar h 🤣🤣🤣

[@roshangupta8161]

15:50 Bro didn't even hesitate!! 😂😂

[@sudipasarkar7981]

areeey you're the best ..i can binge watch your videos

[@aditya-bl5xh]

Get a life

[@subarnasamanta4945]

Attitude tabar tor hai bhai sahi hai dikhra hai kis level ka preparation hai aur really approach kafi different aur accurate hai

[@manaligupta5332]

The current solution is O(N), O(N) for time and space complexity respectively. A more optimized solution exists using constant extra space O(N), O(1).

[@yoyocontact5181]

can you please help me ? I wrote the whole code but it is giving me segmentation fault , i cant find where is the mistake #include #include #include using namespace std; #include int trap(vector& height) { vectormaxl; vectormaxr; maxl[0]=height[0]; for ( int i =1;i=0;i--) { maxr[i]=max(maxr[i+1],height[i]); } vectorwater; for ( int i =0;i

[@ajitdhayal1612]

Jenny kafi achchha padati hai +sunder bhi dikhti hai! Sir aapka crush hai sayad😂

[@TheAdityaVerma]

Tum log badnaam mt kro be, 😂😂 tum logo interest aaye isliye bola tha yaar, yaha to backfire ho gya 😕😅

[@Anand-zg6jv]

Bhai or SB topic pe videos dalo na .... Bhut Shi samjh Mai aata tumhari video se

[@mrinalkhandelwal9631]

Sir, please upload videos on graph problems: DFS, shortest paths, SCC

[@abhishekaggarwal7110]

one line for Jenny 😂 kaafi acha pdhati hai and sundar bhi dikhti hai 😂

[@be_like__prateek]

was expecting the approach using stack. It's nowhere in the utube. DP approach is explained by everyone as it is easy.

[@kirtikhohal3313]

no doubt , he gave an amazing explanation, but we didn't used stack in this solution, then what's the point of adding this question in the stack playlist?

[@strangesoul31]

Still Waiting for Tree,Graph, Backtracking... Bhai apko jab bhi time mile to inki video series bana ke upload kr dena🙏🙏🙏

[@vasupatel635]

You are doing great job. aditya. Thanks man.

[@sbrmnd3885]

Waiting eagerly for your backtracking playlist. Please release it soon.

[@chandankrjha]

itna acche se explain kiya hai. dhanyawaad.

[@yoyocontact5181]

can you please help me ? I wrote the whole code but it is giving me segmentation fault , i cant find where is the mistake #include #include #include using namespace std; #include int trap(vector& height) { vectormaxl; vectormaxr; maxl[0]=height[0]; for ( int i =1;i=0;i--) { maxr[i]=max(maxr[i+1],height[i]); } vectorwater; for ( int i =0;i

[@pratik.784]

stack kha use hua isme?

[@tanzeelurrahman1545]

Add link to problem in your videos. TY for the amazing tutorials.

[@harshtiwari1397]

Thanks sir , please keep uploading as these are very useful videos.

[@sagardas4569]

Btw very good concept i understand through this ❤️❤️

[@uthsyabmandal2258]

GOD BLESS YOU BHAI

[@simrankureel94]

You will very soon have 1M subscribers.

[@muttanashivasaikumar8763]

amazing explanation bhayya..... thank you. and please share the pdf of the notes and ur explationation

[@aishwaryadwani9365]

Now are the days when i search about any topic then i type this -> rain water trapping aditya verma... #God

[@mainaksanyal9515]

Bhai stack kaha use kiya issme ??

[@samareshms4591]

Apke video ko bc kaun bewakoof insaan dislike kar raha hai Kitne acche padha rahe ho aap Aapko jitna like diye toh bhi kam padega THANK YOU BHAYYA!! Keep helping us

[@mohitsoni4352]

jenny fan honge :)

[@adityamane9312]

what will be the time and space complexity for this problem??

[@AmanKumar-kz1rn]

samshj me agya kaise pani nikalna hai thanks bhaiya for such a wonderfull explanation

[@ayushbisht2689]

Loved your way of explaining .

[@Prodcater]

@adityaverma Please discuss the time complexity also for each program ..please it will help a lot

[@RahulVerma-fz2jf]

Upvoting because you explained it well, but the video pic (in the starting) mentions, you will be solving it using stack, but you didn't. Please add the stack solution as well.

[@jaydeepmahajan6598]

Explanation is really good but i didn't see stack in this problem

[@akashbhoi1951]

Sundar bhi dikhti hai woh😂🥰🥰

[@dashrathsinghkaviya]

15:52 That Laughter 😂

[@tanmaymalhotra4450]

Finally Understood, Thank you Bhaiyya !!

[@harshvardhanyadav8949]

Amazing explanation sir ,you make this problem a lot easy

[@jitengarg5740]

bhai bohot badiya thi vedio :) pr avaj bohot kam hai jis karan earphone lagane pad te hai aur jada time earphone lagane muskil hai

[@ShreyaSingh-vr9qi]

Nice explaination !!

[@ajitpai1852]

Nice videos. Video ka volume bahut kam ata hai. Please thoda volum jyada rakhiye

[@PankajGupta-vs2kq]

Time complexity using this method and using stacks is O(n), right?

[@047gauravkumartiwari5]

Bhaiya mic mars pe rakh ke earth pe video record kar rahe ho kya.

[@piyushkumar-bl2ck]

Thanks Aditya . Constant space - O(1). and single loop solution - O(n) void max_water(int A[], int n) { int l = 0, h = n - 1; int left_max = 0; int right_max = 0; int ans[n] = {0}; while (l = right_max) { right_max = A[h]; } else ans[h] = right_max - A[h]; h--; } } for (int i = 0; i < n; i++) { cout

[@kirtikhohal3313]

Is it the dp solution??

[@aryankhanuja4828]

@@kirtikhohal3313 Dp can not be done without memoisation. This is greedy ig..