Trapping Rainwater | Brute | Better | Optimal | with INTUITION

[@takeUforward]

Do leave a comment whether you understood the explanation or not, helps me a lot :) C++ Code Link: github.com/striver79/SDESheet/blob/main/trappingRainWaterC%2B%2B Java Code Link: github.com/striver79/SDESheet/blob/main/trappingRainWaterJava For live session follow at Instagram: instagram.com/striver_79/

[@parikshitrathore1510]

@shashank choudhary he is not making video for growing rather he want to help the community in the best way possible!!...and as we have seen many guus were glad that they use the SDE sheet for there placements so, striver is making the videos so, that sde sheet can be done in less time and more efficiently!!

[@abhishekranjansingh5348]

Seriously wanted this video , thanks bhaiya 😘😘😘😌😌😌

[@suvojitray1431]

great work you have been working real hard for us

[@vaibhavsethia70]

Understood it well.

[@vishalsannapuri208]

Bro only the writing part is not so great so that's the only catch

[@riteshsrivastava3447]

*if you dont know how to calculate prefix max and suffix max , that is really fine u can learn it and continue doing SDE sheet , if u already know everything then u would not be needing any sheet*

[@hikikomori9387]

can you please share a useful link for learning prefix max and suffix max ? i would be thankful

[@vishnuvardhanmalepati7843]

@@hikikomori9387 didn't find any.. Hence sharing the code for prefix max array and suffix max arrays (in Python) l_max = height[0] r_max = height[-1] n = len(height) prefix_max = [0]*n suffix_max = [0]*n # find the prefix maximum array for i in range(n): l_max = max(height[i],l_max) prefix_max[i] = l_max # find the suffix maximum array for i in range(n-1,-1,-1): r_max = max(height[i],r_max) suffix_max[i] = r_max print(prefix_max) print(suffix_max)

[@navendraagrawal]

exactly

[@chetanraghavv]

@@hikikomori9387 think of prefix max array as the array which at any index i contains the max element from index 0 till index i. //prefix max array of array "height" of size n vector left(n,0); left[0] = height[0]; for(int i=1;i=0;i--) right[i] = max(right[i+1], height[i]);

[@hikikomori9387]

@@chetanraghavv I understand now, thank you so much Chetan bhai

[@manojpandey7517]

Striver bhai DSA sheet leke aane waale aap pehle aadmi the. Uske baad saare youtubers DSA sheet leke aa rhe. 😂Par ham abhi bhi aapka hi follow krte hain. Ye legacy aapne hi shuru ki thi.

[@shashankrustagi2812]

ye to mujhe pata hi nahi tha lol.

[@shivamyadav6369]

Video explanations bhai ka best hai plus voice m jo energy hai na wo jagaa k rkhti h

[@pranaykumar9433]

bhai love babbarne laya tha pehle

[@takeUforward]

@@pranaykumar9433 na bhai date dekh lo dono videos k

[@pranaykumar9433]

Bhaiya word wrap question pr ek video bnaiye plz

[@manikantabandla3923]

I feel intuition should precede the algorithm always. That's where the skill of problem-solving comes in.

[@shivanimehta5280]

Had my interview today and coincidentally the interviewer asked me the same problem. Seems like striver knew this beforehand so he dropped this video today only 😄😂

[@takeUforward]

XD

[@511-neelbutani9]

Which company?

[@sandeepdass55]

I really wanted to solve this and had optimal solution in mind but was not able to code it. Thanks to you as i searched a lot on youtube but didn't find better explanation than yours! Keep it up and thanks ^_^

[@prithvigupta8215]

9:22 most optimal solution 16:22 intuition

[@avinashjha6355]

brother..i am waiting for you to finish all the problems in dsa sheet..you explain very well..please try to bring all the videos fast

[@piyushkumar-wg8cv]

I didn't know what is suffix max and prefix max, but now that I know what is suffix and prefix array I can compute it. I will continue with the SDE sheet also. Don't demotivate.

[@harshtank7075]

That optimized explaination with intuition went directly inside my head. Thank you brother 👍

[@takeUforward]

Perfect!

[@freshcontent3729]

can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?

[@freshcontent3729]

is this solution under DP ? if yes then why is it under DP ?

[@krishnasai3367]

@@freshcontent3729 kzbin.info/www/bejne/jp_Koo2KhsiEaac&ab_channel=ClubofProgrammers%2CIITBHUVaranasi

[@manistrikes]

@@freshcontent3729 making the prefix and suffix sum for further use takes this question to DP dimension...because we are storing the largest element till a particular index for the further use...so it's kind of memoization..dp thing...

[@bhaveshkumar6842]

You are the most effective teacher and I am immensely grateful for your work.

[@datamining4655]

Why are we checking whether a[l]< a[r]? Isn't it more intuitive to check whether leftMax

[@kshittizbhardwaj417]

Yes, you are right you can check that also even I did it the same way. It just depends upon which intuition strikes us first

[@ritshpatidar]

The hardest part is after coming up with idea that we need to use two pointer. I had the idea but was unable to think, how can I take advantage of two pointers. My thinking says that if you know two pointers can solve this then always try to make values equal. If value at one pointer is less than other, and increment it towards other in order to find greater value.

[@iamnottech8918]

Like omg the optimal solution explanation is of next level

[@kalpkumudkumar8163]

took me 2 times to understand intuition but this is best video you can get on this problem , good work .

[@JayTharwani]

This is a great explanation with patience ! Thank you for sharing .

[@ghoshdipan]

GOD LEVEL EXPLAINATION!

[@gandhijainamgunvantkumar6783]

the last approach explanation was amazing. Thank you so much brother. :)

[@SAICHARANREDDYN-wk9zk]

that intuition that you explained at the end cleared all my doubts and got me a solid understanding! perfect 🥳

[@mukulbindal2303]

Bro, honestly, I will still feel like I am being dishonest to the interviewer. I mean I can't explain this solution to him with a straight face.

[@takeUforward]

It's not about how you feel, it's about understanding these things, and keep on solving a new problem every day. if you are able to solve every problem, how will you learn, the more you cannot solve, the more you learn.

[@mukulbindal2303]

@@takeUforward it's the fear of getting caught. Thanks btw. : )

[@takeUforward]

@@mukulbindal2303 u are not cheating :) even the interviewer knows you have prepared from leetcode. No one expects you to come without preparing so chill out.

[@mukulbindal2303]

@@takeUforward Oh.. I didn't know that side.. If that's what it is, then no need to worry. Thanks Raj bro : )

[@sanjayjoshi8807]

@@takeUforward bhaiya if we are given with the width array also for respective building then we have to compute area ? make a video on it

[@Rajat_maurya]

whenever i stuck in a problem i search if u have made any video on that...love u

[@nalingoyal881]

We can always increase l and r when the height[l]

[@stith_pragya]

Understood....Thank You So Much for this wonderful video..................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@YashHalgaonkar]

I came here only to revise the two pointer method. Time stamps will be very helpful.

[@Ace-ex9gg]

calculating suffix and prefix is one of the most basic question . I don't know why people complain about this sheet. Striver is a 6* coder and just imagine how would he feel about wasting time on that prefix and suffix.!!!!

[@akashvaidsingh]

One request, it will we very helpful if you add timestamp for each approach.

[@rohansinghjr1195]

Brother I've seen some of the interviewers don't like,and said that if you know the optimal solution why not came up with it on first approach.... How to tackle that! Thanks in advance

[@kshittizbhardwaj417]

did you get any answer?

[@varunsharma5582]

Don't act like you know the optimal solution, struggle, talk to them, take hints and act like you made the solution based on their hints slowly.

[@priyankapatil6783]

Hi Raj, Can you please explain about this problem "Interleaving Strings "

[@santanu29]

I got the intuition when you explained the left pointer shifting. Did the rest by myself. Thank you for the video.

[@saliqgowhar395]

you are for sure the best teacher India has ever seen ! 😀

[@anupamdubey5736]

Watched this video after Aditya Verma's for best solution with 2-pointer approach. Although, took some time to understand maxLeft and maxRight parts in 2-pointer but good learning took place. Thanks a lot Raj.♥️

[@saichand1940]

This is the best explanation I can ever find on yt for this problem... respect++;

[@subhamengine1143]

just saw the first 7 min and tried on my own.. and i solved it.. thanks..striver.

[@leetcodebaby6680]

If you're looking for the code of the bruteforce approach that he mentioned then here you go: class Solution { public int trap(int[] height) { int units=0; for(int i=0; i

[@RGMUTEX]

Thanks a lot bro. So nice explanation..❤

[@maneeshkumarpatel9874]

That's the awesome solution. Thanks a lot Striver💓

[@soumyadebbasu7882]

Thank you Dada for your efforts !

[@sanoferniswan5901]

Really so helpful to understand better.. Thanks for sharing🎉

[@fromdjangoimport__help__3585]

use long long for storing ans if u r getting error

[@kartikeyasingh5172]

2 pointer solution is mind blowing

[@harshagarwal1218]

Great Explanation! The way u emphasize on the intuition makes it easy to grasp it.

[@freshcontent3729]

is this solution under DP ? if yes then why is it under DP ?

[@de-codr8814]

this is the best explanation available on youtube for this problem .👌👌👍😲

[@yashgoyal7999]

wonderful explanation, you explained it so easily, thanks striver🙂🙂

[@prakharagarwal6237]

Simply beautiful✨✨ Thanks!

[@freshcontent3729]

is this solution under DP ? if yes then why is it under DP ?

[@prakharagarwal6237]

@@freshcontent3729 no it's not DP

[@freshcontent3729]

@@prakharagarwal6237 then how can we do it using dp ?

[@kage-musha1702]

Solutions and intuition are crystal clear as always bro

[@manavmohata1240]

All the best!

[@kage-musha1702]

@@manavmohata1240 Thanks bro All the best for you too :)

[@mickyman753]

did you got placed

[@kage-musha1702]

@@mickyman753 yea its a small company thou , i've got an opportunity as paid intern , if it goes well along they said they'll recruit for full time employee :D :)

[@mickyman753]

@@kage-musha1702 All the best buddy , keep going and stay healthy

[@AbhishekVerma-yw1ps]

Ye video 20 Dec 2020 ki hai and Love bhaiya ki 14 Oct 2020 ki hai. Iska matlab unki sheet pehle aayi thi

[@vivekpatel6721]

I know striver you will reply to me but still I have a doubt that why have we used here this if condition height[left]

[@SaurabhSingh-vg5vr]

he is telling solution like gospel truths for life problems

[@kunalkhandelwal5782]

Such a great explanation...thanks a lot.

[@ad8331]

Not a HIndi speaker, but I prefer that you also release Hindi explaination video of the problem. It is difficult to understand the logic in english, but will be easier to explain in English once understood in a familiar langauge. Just a genuine request.

[@Ak-um1yg]

Global audience is the main target .. I guess

[@roushanraj8530]

Bhya, explanation is too good, understood 💥💥💯

[@sayantaniguha8519]

How does the optimized logic give correct answer for a sorted array ?

[@-Corvo_Attano]

if the array is sorted , water will drain to the bottom.

[@anandkumar.3307]

finally i understood thanks a lot !!

[@sbarbeloa]

Sir hats off to you for the optimal solution. Also wishing you a speedy recovery

[@sourabhsisodia9563]

Bhai mjaa aa gya .... Kya samjhaya hain.... Tumhare videos litreally above expectation hote hain...Majaa AA gya striver bhai

[@freshcontent3729]

is this solution under DP ? if yes then why is it under DP ?

[@sourabhsisodia9563]

@@freshcontent3729 no it's not under dp

[@freshcontent3729]

@@sourabhsisodia9563 then how can i do it using dp ?

[@sourabhsisodia9563]

@@freshcontent3729 i am just a beginner... Not started learning dp yet....If you want to know then just google it

[@RohitSingh-hs4hv]

Thank You Striver For this awesome Sheet

[@dontknow592]

Thank You Sir. Bahot mast samjhaate hain. Aap🔥

[@anshvashisht8519]

7:15 what is prefix and suffix here?

[@freshcontent3729]

is this solution under DP ? if yes then why is it under DP ?

[@sandeepnallala48]

Hi brother, i am new to this channel.. loved your vedios, In this prblm how can we directly come up with that solution you taught with two pointers, If we are actually seeing the prbln for the frst time?? The Intuition behind it also is not so staight forward?? I think we can think of that approach after seeing someones code or taking external help.. i want to ask onething bro, when u were doing it for the frst time, whether the same prblm with you or you got it right away??

[@manikantabandla3923]

You are just teaching how to memorise the solutions.

[@rishukumarsingh3926]

How do they think of such a great logic?...

[@bhavyavijay0]

how to compute the prefix max and suff max??

[@-Corvo_Attano]

Striver's explanation is always perfect :)

[@OilUp96]

Thank you striver

[@gokulreddy709]

Hey I am new to competitive coding and want to understand time complexity better can you make a video about. It will help me a lot. Thank You

[@lokeshvikram6192]

very well xplained bro.I got the intuition

[@prahladbhadani]

can't thank you enough for such superb explanation

[@tanmay9928]

Really recommend watching this video at 1x speed.

[@sharanpreetchadha3579]

Hey, I got the logic of solving the problem like when a[r]

[@takeUforward]

I have answered this in the last portion, just before discussing the time complexity. You can watch it once, and let me know if there is till a doubt.

[@prasantharavindramesh1078]

Bro awesome explanation. Just a follow up question. If the bars are of varying width then what will be the approach? Can I use array of struts to store width and height of each bar ?

[@Kaivalyamani]

Question remains same ...water stored depends on the height ....and unit can be calculated using formula of rectangle which must be given in the problem

[@freshcontent3729]

is this solution under DP ? if yes then why is it under DP ?

[@nishantsrivastava2931]

great video...can u make the videos on the sde sheet section of dp first...just can't wait for such an awesome explanation of dp problems...

[@freshcontent3729]

can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?

[@niitteenpathak8303]

Very Good Explanation👏👏👏👏👏👏👏

[@ankitkumarmishra5198]

Brute force approach: class Solution { public: int trap(vector& height) { int ans=0; for(auto i=0;i

[@freshcontent3729]

can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?

[@ganapatibiswas5858]

This is Great Explanation

[@shivnathsinghgaur5972]

Optimal solution from 8.50

[@parthh1112]

class Solution { public: int trap(vector& v) { int ans = 0; vector lm(v.size(),-1); vector rm(v.size(),-1); int maxx = INT_MIN; for(int i=0;i=0;i--){ if(maxx < v[i]){ maxx = v[i]; } rm[i] = maxx; } for(int i=0;i

[@myyoutubeisthis]

Thank you very much sir.

[@18devpratapsingh33]

C++ solution class Solution { public: int trap(vector& height) { int sum = 0; int n = height.size(); vector prefix(n,0); //leftsum vector suffix(n,0); // rightsum; // computing leftsum ; prefix[0] = height[0]; for(int i=1;i=0;i--){ suffix[i] = max(suffix[i+1],height[i]); } for(int i=0;i

[@snehalsamale7404]

Code provided in the discription giving wrong answer!

[@Impromptu21]

What if it is 3,0,1

[@takeUforward]

The code is there, just put some cout statements and you will get how the loops runs

[@shivalikagupta3433]

Extremely well explained!!! :))))

[@parikshitrathore1510]

Understood Bhaiya!!😍😍🤩🤩

[@Shivi32590]

thank you

[@aadityakhetan956]

Hats off to your efforts 👏 very nicely explained 🙌🙌

[@avishkarghadge509]

Is prefix sum same as prefix max array ? what is suffix max array ? seeing prefix max in code it just probably keeping maximum till known point but same logic couldnt translate to suffix max array Any links to articles ??

[@spandanrastogi7144]

JAVA : PrefixMax and SuffixMax Solution : public int trap(int[] height) { int[] prefixMax = new int[height.length]; int max = 0; for(int i=0; i=0; i--){ max = Math.max(max, height[i]); suffixMax[i] = max; } int water = 0; for(int i=0; i

[@mayurigawande5973]

You are great man🤗may your all dreams come true😍🙌

[@KishoreKumar-xr3fu]

Hi bro, could you please share the similar problems or if already shared those links where we can solve with prefix and suffix array(2nd approach in this video)

[@jitinroy2246]

you can watch anuj bhaiya video on 2nd approach, search tapping rainwater problem on youtube.

[@dayashankarlakhotia4943]

Very good explanation

[@parthvaghela7820]

Maza aa gaya bhai. Superb work!!!

[@manojnavinjamuri5867]

i didnt udnerstand this explanation. please include sub titles.

[@prashantraj6366]

I want to share 1 more approach It's a brute force and may lead to undesired triversal but easy to understand int trap(vector& v) { int m=0; for(int k:v){ m=max(k,m); } int ans=0; int st=0,en=v.size(); for(int j=0;j

[@shubhankurkumar539]

Thanks!

[@mantrarajgotecha3055]

Best explanation ever on youtube :))

[@rejetimeghavardhan7805]

Thanks a lot for the video such a good content understood very well

[@freshcontent3729]

is this solution under DP ? if yes then why is it under DP ?

[@rejetimeghavardhan7805]

@@freshcontent3729 bro I forgot the solution I will once again go through it and tell the reason

[@pranav288]

7:20 Went through half the sde sheet understanding everything and bro said you shouldn't do it :(

[@be_like__prateek]

@take U forward Yaar is two-pointer approach me to interviewer pakka samajh jayega ki is bande ne pahle ye kiya h....to fir usse kya bolenge ? I mean uske samne kese loudly sochna hai ?

[@takeUforward]

Islie brute fir prefix fir 2 pointer pe jaana h, time gap lena hai, and interviewers ko bhi pata rahta hai u have prepared so chill rhta hai!

[@abdullasulfikkar5282]

@@takeUforward but bhaiya what if there is a time limit? Like if the interview is for 1 hour only?

[@be_like__prateek]

@@takeUforward thanks bhai!!!

[@sounaksaha1455]

Beautiful video sir

[@piyushverma8207]

I just like your videos before even watching