L8. Trapping Rainwater | 2 Approaches | Stack and Queue Playlist

[@brokegod5871]

the prefix/suffix match approach is a lot better to understand imo

[@nomi98]

I think people can't understand this one from any of the available videos because they're glossing over some things, which either they don't understand or they find not worth mention (or simply forget). I just wrote down step by step how I would solve it with two pointers and figured out why they were doing what they were doing. I finally understand this shit 😭.

[@kulyashdahiya2529]

it's a DP apprach.

[@prasenjitsutradhar3368]

I want to be honest here-this is probably the first time I’ve struggled to clearly understand Striver’s explanation! 😭😭😭 Previously, I learned the stack topic from Aditya Verma as Striver’s videos weren’t available then. For all other topics, I’ve relied on Striver and have never found any approach difficult to grasp. However, this time, I barely understood the explanation for the second approach. I would sincerely request Striver to consider re-recording this portion to provide more clarity and replace the existing video.🙏🙏🙏

[@b_technical4017]

Striver you don't know how much this is helping us!! Thank you so so so Much! No one can explain DSA better than you❤❤😭

[@shreyxnsh.14]

wrong problem to say this, barely anyone understood what he said in the second approach

[@rwordspecialist6734]

Fr😂😂​@@shreyxnsh.14 gotta see once more will see what I'm missing

[@Sonu.Singh.28]

Simple thought process: On top a building we can store some water if the there is a building on both left and right with height greater than the current building. And the amount of water stored on top of the building would be the min height of those left and right building minus the height of current building.

[@anujbalwada5211]

Thanks a lot bro 🤗 with this single thought , I have implemented it easily .

[@kartiksaini-xn6ke]

16:46, arr[i] has to be *smaller* than and NOT greater than leftMax and rightMax to store water on top of it

[@rushidesai2836]

The way you explained the second approach is commendable.

[@subratkumarsahoo3785]

Totally confused in the better approach!!😢I think the bruteforce approach is better..

[@farchit9467]

if h[l] < h[r], meaning the right can handle the water thus we don't need to worry about the right half, thus we check the left half if we have a taller building (leftMax) to store water & act accordingly. lly for the h[l] > h[r].... for h[l] == h[r] move any doesn't matter

[@chad._life]

better is cup cake

[@sonalidutta825]

read my comment. you'll get the gist of it. 😇

[@vamsikrishnagannamaneni912]

@@farchit9467 what does llly mean dude?

[@jyotikajaichand1982]

@@vamsikrishnagannamaneni912 similarly

[@hashcodez757]

CORRECTION-> 22:51 we have to take the smaller one

[@omkarshendge5438]

yup exactly we will go with the smaller one.

[@riyaraj5720]

yess

[@nitinxd98]

i watched this video three times again for the opetimal approach and got confused as soon as he took the 2 instead of 1 thanks for clearing

[@lillyput2275]

Yes I watched many times and thought to put this comment and found ur comment 😅

[@oyeesharme]

yeah bro

[@sonalidutta825]

if you understood the prefix/sufix approach, you'll get the 2pointer approach as well !!!! 1. why L and R meet at the highest height? -> since we are processing left/right side based on whichever is the smallest. at some index Left_max is less than Rightt_max => process left , update Left_max now as soon as Left_max becomes greater than Rightt_max => start processing right, update Rightt_max....continue 2. why 2 pointer? amount = min(Left_max,Rightt_max) - curr_height; (and amount should be greater than 0 obvoiusly!) from prefix and suffix logic: min(Left_max,Rightt_max) => if at some point Left_max is minimum then for any next index right_max can be minimum only when left_max is updated to a bigger value. note: values of Left_max & Rightt_max can't be reduced. we are taking minimum out of bigger and bigger. coming to 2ptr now for any index L from start (i.e left) I need min(Left_max, Rightt_max). suppose for that index left_max till L-1 is less than right_max till some index R. do u think we need to calculate right_max till L+1 knowing that value of right_max won't reduce and we need the min(Left_max,Rightt_max). answer is no. Reason? -> right_max is only going to increase. so the left_max is already the minimum. then why the heck you'd calculate right_max till L+1 , isn't it great? happy coding!!🙌🏼☺

[@sonalidutta825]

class Solution { public: int trap(vector& height) { int n = height.size(); int l=0, r=n-1, l_max=0,r_max=0, ans=0; while(l

[@shikher4559]

Striver heap playlist is needed please!

[@souravmohanty834]

The optimal approach would definitely not strike in an interview if not revisited😂

[@Aksht-h9u]

your reminder to revisit

[@Imtiyazbhai-ox9dg]

@@Aksht-h9u ++

[@Gurunat16]

For better understanding, consider L, R, (either of) leftMax or rightMax as buildings (Building of 3)..... To trap water it should satisfy any one of the combinations... leftMax > L < R L > R < rightMax Remember you always first look at the L and R. Then decide which one to choose among leftMax or rightMax. Next doubt might be, how it works for same L and R... If L == R, then we can apply it to both of the above combinations. leftMax > L == R -> Wont be valid.... Because leftMax cannot be greater than R (Thats how we iterate thru the arr). Same way for another combination as well.

[@ugthesep5706]

Learned a new approach I didn't know the second approach previously. I solved this problem by approach 1 on my own a few weeks ago♥

[@KrishnaSingh-rd6pr]

Dropping stack playlist in a queue Noice

[@MadirajuPhaniSaiSrinivas]

Corrections in video : 16:46 & 22:51 - Take Smaller One*

[@sujalthakkar2118]

22:51 - shouldn't we have to take the smaller one here? please correct it. and in the portion of describing the intuition of Optimal approach as well, you said that arr[i] will always have to be greater where it's the opposite. thank you concept was crystal cleared 💌💌

[@bilalshaikh5648]

hey Striver hope you are doing extremely. Just had a small request to update these video links on the take U forward A2Z DSA sheet.

[@killerboy2387]

Striver we want Heap playlist its important in intership round there is question of heap

[@AyushEditz-hs6pf]

Why is this in stack and queue playlist? Shouldn't this be int the 2 pointer and Sliding window playlist??

[@Enigm.1.]

exactly

[@apmotivationakashparmar722]

Thank you Striver for great explaination 😀🙏

[@Ekam873]

i did one thing i traverse from the left and find next greater or equal element except for zero and then we can subtract indexs -1 and that will give the unites of water logged and sum it up that's how you will be using stack to find next smaller element

[@zenmonk29]

i did the same.but code is a bit errenous. can u share the code please

[@esmamanyt7048]

my thought process was same but fucked up while writing code

[@kaichang8186]

understood, thanks for the perfect explanation

[@AyanAbbas-ps8xv]

for the very first time solved a hard problem in a single go

[@prathameshjadhav2942]

I strongly advise that if not understood Better Approach then Dry run of pseudo code..

[@chad._life]

but i just want to say your explanation is best out of all ............

[@swarupdas4114]

Optimal Solution 15:40

[@arnavjain6038]

Please link problem on code 360 in description. Great Video as always!

[@hashcodez757]

bhai na toh stack use hua na hi queue 🥲😅

[@oyeesharme]

optimal solution 🤐

[@samiranroyy1700]

sir Understood Nice Explanation🥰🥰

[@DhananjayKumar-rr3jc]

Amazing optimal solution

[@RanjanKumar-pm4bc]

Aree dhano 😅

[@RanjanKumar-pm4bc]

Optimal samjh aa gaye be ???? Aate h room pe

[@Adarsh_agrahari]

thanks u bhaiya for this quality content

[@mayukhbhowmik934]

Bro Made stack question a two pointer question!!!

[@gautamsaxena4647]

understood bhaiya

[@omkarshendge5438]

arr[i] has to be strictly less than leftmax and rightmax this is the correction folks pls take care of.

[@yashpaunikar671]

Yes. He mistakenly said greater

[@udaypaul77]

great explanation

[@Sridhar-fd5qr]

Dry run, you will understand the intuition

[@aashikroy2198]

Solution using Stack : public static long getTrappedWater(long []height, int n) { long totalWater = 0; Stack stack = new Stack(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int bottom = stack.pop(); // Index of the bar at the bottom if (stack.isEmpty()) { break; } int left = stack.peek(); int right = i; int width = right - left - 1; long heightOfWater = Math.min(height[left], height[right]) - height[bottom]; totalWater += width * heightOfWater; } stack.push(i); } return totalWater;

[@Sanyam7208]

Doubt Ye pure process me stack kaha use hua jo ye stack ka topic ha

[@sauravfarkade1928]

Understood!! cout

[@vamsikrishnagannamaneni912]

Why are we incrementing the smaller one in O(1) SC approach?

[@AkshayVaghela-o9c]

22:57 l=1 and r=2 then why you choose r=2 we have to choose smaller one right ??

[@hashcodez757]

same doubt??

[@abishailovelson1614]

prolly mistake

[@omkarshendge5438]

a mistake we should take lmax = 1 here he did a typo, pls take a note of it

[@KarumuriYasaswini]

optimal soln 😵

[@aayush5474]

aadhe ghante ki video dekhli na stack use hua na queue

[@swadhinsahoo2846]

16:46 it has to be smaller not greater

[@OmPrasad-x9u]

Nice Explanation

[@KeerthiReddyKolan]

But neither stack nor queue is used? 🤔🤔

[@Ekam873]

did one thing i traverse from the left and find next greater or equal element except for zero and then we can subtract indexs -1 and that will give the unites of water logged and sum it up that's how you will be using stack to find next smaller element

[@Aksht-h9u]

@@Ekam873 can you explain more or share your code please

[@aashikroy2198]

I thought he would explain the approach by using stack as well.

[@samiranroyy1700]

class Solution { public int trap(int[] height) { int n= height.length; int left[]= new int[n]; int right[] = new int[n]; left[0]=height[0]; for(int i=1;i=0;j--) { right[j]=Math.max(right[j+1],height[j]); } int ans=0; for(int y=0;y

[@sibiranganath]

why is this problem is under stack and queue playlist

[@nikhiljain-nl7rs]

if condition is not needed in the last loop

[@firebout7675]

class Solution { public: int trap(vector& h) { vector left(h.size(), 0); vector right(h.size(), 0); int maxi = INT_MIN; for(int i=0; i maxi){ maxi = h[i]; left[i] = maxi; } else{ left[i] = maxi; } } maxi = INT_MIN; for(int i=h.size()-1; i>=0; i--){ if(h[i] > maxi){ maxi = h[i]; right[i] = maxi; } else{ right[i] = maxi; } } int ans =0; for(int i=0; i

[@DeadPoolx1712]

UNDERSTOOD;

[@themusicguy539]

void lefty(vector&height,vector&prefix){ prefix[0]=height[0]; for(int j=1;j=0;j--){ suffix[j]=max(height[j],suffix[j+1]); } } int trap(vector& height) { int total=0; int n=height.size(); vectorprefix(n); vectorsuffix(n); lefty(height,prefix); righty(height,suffix); for(int i=0;i

[@ddevarapaga5134]

Understood

[@lokesh8660]

How can we do it using just the suffix sum

[@sanketatmaram]

understood!

[@SapanaDashoni]

Definitely unable to make better approach at interview

[@THOSHI-cn6hg]

two pointer approach is better

[@subee128]

Thanks

[@KartikeyTT]

tysm sir

[@KartikeyTT]

ye stack and queue ka question to nhi h fir is playlist me kyu h

[@yashverma2071]

Bhai tu padh na

[@vasuchourasia8021]

good question🥸

[@mohanappriyakarunakaran]

Fine but where do we use stack ir queue here🤔

[@chitranshverma1822]

for the first approach which should have been easier was not able to code it up on leetcode....its just soo hard, it throws runtime error to me ....i know that i must be putting some minute error but still i am crying in tears and frustrated as hell PS- i am sitting and doing this question since 2 hours now

[@themusicguy539]

void lefty(vector&height,vector&prefix){ prefix[0]=height[0]; for(int j=1;j=0;j--){ suffix[j]=max(height[j],suffix[j+1]); } } int trap(vector& height) { int total=0; int n=height.size(); vectorprefix(n); vectorsuffix(n); lefty(height,prefix); righty(height,suffix); for(int i=0;i

[@madhu_mohanreddy]

second approach is better

[@KUMARSAURABH-s5i]

for vectors use pass by reference

[@abhishekc3556]

class Solution { public: int trap(vector &height) { int n = height.size(); if (n == 0) return 0; int left[n]; left[0] = height[0]; int i = 1; while (i < n) { left[i] = max(left[i - 1], height[i]); i++; } int rightMax = INT_MIN; int totalWater = 0; for (int i = n - 1; i >= 0; i--) { rightMax = max(rightMax, height[i]); totalWater += min(left[i], rightMax) - height[i]; } return totalWater; } };

[@scruffymakaveli6870]

I have a question Striver, why is this in your stack and queue playlist? We didn't use any stack or queue to solve this problem

[@MuraliSriramula-lm4zt]

where does stack used here?

[@AmandeepSingh-rd6ql]

Why traversing the smaller one someone can tell .?

[@dhruvkhanna2410]

if you traverse the greater one, how can you store the water? draw a curve for the array and think....you will understand!

[@dhruvkhanna2410]

i will look like a container

[@AmandeepSingh-rd6ql]

@@dhruvkhanna2410 thanks bro for the help

[@rishabhkansal5811]

Why in l and r we always choose smaller building?

[@rallapatijayasailakshmi1585]

the basic equation for calculating the water is water = Min (leftMax,RightMax) - currentHeight , since we are choosing the min of left and right , we are only intrested in getting the smaller building always

[@AkOp-bf9vm]

i have a question ... we done both approach without stack then why this question is in stack playlist??

[@n5678--]

Isme stack queue ka use kahan hua??

[@Bhargob_Lahon]

stack toh use hi nhi ho rha , toh stack playlist me kiu h ye

[@pranaymishra5456]

why this video is in stack and queue playlist? There is no use of stack or queue

[@sibiranganath]

daam man

[@Ayush37262]

Why this question is marked as hard on leetcode??

[@subhajitdey135]

because its hard man :) prolly due to the optimal approach

[@gaminghouse7861]

explanation is not too good , begineer will never git it.

[@GaneshBhutekar-nu1gd]

thanks

[@aryankumar3018]

Understood

[@rutujashelke4208]

Understood