Trapping Rainwater | Brute | Better | Optimal | with INTUITION
Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE)
✅Entire Series: bit.ly/placementSeries
✅Problem link: leetcode.com/problems/trappin...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
Пікірлер: 279
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
3 жыл бұрын
@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
3 жыл бұрын
Seriously wanted this video , thanks bhaiya 😘😘😘😌😌😌
@suvojitray1431
3 жыл бұрын
great work you have been working real hard for us
@vaibhavsethia70
3 жыл бұрын
Understood it well.
@vishalsannapuri208
3 жыл бұрын
Bro only the writing part is not so great so that's the only catch
*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
2 жыл бұрын
can you please share a useful link for learning prefix max and suffix max ? i would be thankful
@vishnuvardhanmalepati7843
2 жыл бұрын
@@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
2 жыл бұрын
exactly
@chetanraghavv
2 жыл бұрын
@@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
2 жыл бұрын
@@chetanraghavv I understand now, thank you so much Chetan bhai
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
3 жыл бұрын
ye to mujhe pata hi nahi tha lol.
@shivamyadav6369
3 жыл бұрын
Video explanations bhai ka best hai plus voice m jo energy hai na wo jagaa k rkhti h
@pranaykumar9433
2 жыл бұрын
bhai love babbarne laya tha pehle
@takeUforward
2 жыл бұрын
@@pranaykumar9433 na bhai date dekh lo dono videos k
@pranaykumar9433
2 жыл бұрын
Bhaiya word wrap question pr ek video bnaiye plz
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
3 жыл бұрын
XD
@511-neelbutani9
3 жыл бұрын
Which company?
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 ^_^
I feel intuition should precede the algorithm always. That's where the skill of problem-solving comes in.
took me 2 times to understand intuition but this is best video you can get on this problem , good work .
You are the most effective teacher and I am immensely grateful for your work.
That optimized explaination with intuition went directly inside my head. Thank you brother 👍
@takeUforward
3 жыл бұрын
Perfect!
@freshcontent3729
3 жыл бұрын
can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?
@freshcontent3729
3 жыл бұрын
is this solution under DP ? if yes then why is it under DP ?
@krishnasai3367
2 жыл бұрын
@@freshcontent3729 kzread.info/dash/bejne/iqKb07yNgca3Y6g.html&ab_channel=ClubofProgrammers%2CIITBHUVaranasi
@manistrikes
2 жыл бұрын
@@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...
I got the intuition when you explained the left pointer shifting. Did the rest by myself. Thank you for the video.
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.
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.
the last approach explanation was amazing. Thank you so much brother. :)
Why are we checking whether a[l]< a[r]? Isn't it more intuitive to check whether leftMax
@kshittizbhardwaj417
3 жыл бұрын
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
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
that intuition that you explained at the end cleared all my doubts and got me a solid understanding! perfect 🥳
9:22 most optimal solution 16:22 intuition
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
3 жыл бұрын
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
3 жыл бұрын
@@takeUforward it's the fear of getting caught. Thanks btw. : )
@takeUforward
3 жыл бұрын
@@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
3 жыл бұрын
@@takeUforward Oh.. I didn't know that side.. If that's what it is, then no need to worry. Thanks Raj bro : )
@sanjayjoshi8807
3 жыл бұрын
@@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
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.♥️
Great Explanation! The way u emphasize on the intuition makes it easy to grasp it.
@freshcontent3729
3 жыл бұрын
is this solution under DP ? if yes then why is it under DP ?
Hey, I got the logic of solving the problem like when a[r]
@takeUforward
3 жыл бұрын
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.
whenever i stuck in a problem i search if u have made any video on that...love u
This is the best explanation I can ever find on yt for this problem... respect++;
Sir hats off to you for the optimal solution. Also wishing you a speedy recovery
This is a great explanation with patience ! Thank you for sharing .
GOD LEVEL EXPLAINATION!
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??
this is the best explanation available on youtube for this problem .👌👌👍😲
how to compute the prefix max and suff max??
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]
can't thank you enough for such superb explanation
Understood....Thank You So Much for this wonderful video..................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
That's the awesome solution. Thanks a lot Striver💓
very well xplained bro.I got the intuition
Thank you Dada for your efforts !
just saw the first 7 min and tried on my own.. and i solved it.. thanks..striver.
wonderful explanation, you explained it so easily, thanks striver🙂🙂
We can always increase l and r when the height[l]
This one is amazing.... Very Well explained
Thank You Striver For this awesome Sheet
Thank You Sir. Bahot mast samjhaate hain. Aap🔥
Really so helpful to understand better.. Thanks for sharing🎉
you are for sure the best teacher India has ever seen ! 😀
Bhya, explanation is too good, understood 💥💥💯
Solutions and intuition are crystal clear as always bro
@manavmohata1240
3 жыл бұрын
All the best!
@kage-musha1702
3 жыл бұрын
@@manavmohata1240 Thanks bro All the best for you too :)
@mickyman753
3 жыл бұрын
did you got placed
@kage-musha1702
3 жыл бұрын
@@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
3 жыл бұрын
@@kage-musha1702 All the best buddy , keep going and stay healthy
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
2 жыл бұрын
you can watch anuj bhaiya video on 2nd approach, search tapping rainwater problem on youtube.
is this solution under DP ? if yes then why is it under DP ?
I came here only to revise the two pointer method. Time stamps will be very helpful.
Striver's explanation is always perfect :)
finally i understood thanks a lot !!
Such a great explanation...thanks a lot.
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
3 жыл бұрын
did you get any answer?
@varunsharma5582
2 жыл бұрын
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.
Extremely well explained!!! :))))
You are great man🤗may your all dreams come true😍🙌
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
Hi Raj, Can you please explain about this problem "Interleaving Strings "
7:15 what is prefix and suffix here?
can we use a vector of tuples for taking the input of the elements (provided we are not already provided with the array through reference as a part of function type problems) and modify each element there on to store the values of the left max, the current element and the right max respectively and then compute the area of water stored by each element and then compute the total area as a sum of the individual areas ?
@takeUforward
3 жыл бұрын
yes if not given, but generally you are given an array only. That is how the interview goes, and also if you stores tuples, every index stores 3 elements, then also sc is 3n.
Legendary explanation !!! Thanks Bhaiya 🧡
Thanks a lot bro. So nice explanation..❤
Hats off to your efforts 👏 very nicely explained 🙌🙌
Brute force approach: class Solution { public: int trap(vector& height) { int ans=0; for(auto i=0;i
@freshcontent3729
3 жыл бұрын
can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?
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 ??
Simply beautiful✨✨ Thanks!
@freshcontent3729
3 жыл бұрын
is this solution under DP ? if yes then why is it under DP ?
@prakharagarwal6237
3 жыл бұрын
@@freshcontent3729 no it's not DP
@freshcontent3729
3 жыл бұрын
@@prakharagarwal6237 then how can we do it using dp ?
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.
One request, it will we very helpful if you add timestamp for each approach.
Love it !
Like omg the optimal solution explanation is of next level
Bhai mjaa aa gya .... Kya samjhaya hain.... Tumhare videos litreally above expectation hote hain...Majaa AA gya striver bhai
@freshcontent3729
3 жыл бұрын
is this solution under DP ? if yes then why is it under DP ?
@sourabhsisodia9563
3 жыл бұрын
@@freshcontent3729 no it's not under dp
@freshcontent3729
3 жыл бұрын
@@sourabhsisodia9563 then how can i do it using dp ?
@sourabhsisodia9563
3 жыл бұрын
@@freshcontent3729 i am just a beginner... Not started learning dp yet....If you want to know then just google it
Very Good Explanation👏👏👏👏👏👏👏
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
3 жыл бұрын
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
3 жыл бұрын
is this solution under DP ? if yes then why is it under DP ?
very good explanation .. good job keep going
use long long for storing ans if u r getting error
Understood Bhaiya!!😍😍🤩🤩
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
3 жыл бұрын
can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?
You are genius bhaiya , what a observation 👌👌
Awesome bhaiya great explanation.
Ooooooooof what an amazing explanation 😷✌️🔥
Thanks a lot for the video such a good content understood very well
@freshcontent3729
3 жыл бұрын
is this solution under DP ? if yes then why is it under DP ?
@rejetimeghavardhan7805
3 жыл бұрын
@@freshcontent3729 bro I forgot the solution I will once again go through it and tell the reason
Bhai Bhai Bhai Bhai !!! OP Explaination 💖💖 Maza aagya 💯
Ye video 20 Dec 2020 ki hai and Love bhaiya ki 14 Oct 2020 ki hai. Iska matlab unki sheet pehle aayi thi
This is Great Explanation
Thank you striver
Thanks!
Thank you very much sir.
is it possible that interviewer ask the solution which is using stack?
@takeUforward
3 жыл бұрын
No it does not works like that. It is not a history test :P only problem is given, how you solve depends on you.
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
Best explanation ever on youtube :))
Maza aa gaya bhai. Superb work!!!
great explaination
Code provided in the discription giving wrong answer!
man! you are brilliant 😍
Very good explanation
7:20 Went through half the sde sheet understanding everything and bro said you shouldn't do it :(
best explanation sir , thankyou
Bhaiya kya aap CodeForces and CodeChef ke solutions ke upar regular video bna sktey ho kya ?
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.!!!!
Thank you so much sir🥺🥺🥺🥺🥺
Thanks bro😍🤗
Striver bhaiya op 🔥🔥🔥