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.

[@sudipsarkar1512]

​@@kulyashdahiya2529 how so, bro ?

[@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

[@ajaymishra1511]

@@shreyxnsh.14 well this problem is actually pretty hard to explain you will need to imagine the whats actually happening

[@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 .

[@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 😅

[@oyeshxrme]

yeah bro

[@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

[@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

[@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.🙏🙏🙏

[@parasarora5869]

Sometimes we don't understand the why behind someone else's thinking. Give it some time and try yourself to find why it works. I also didn't get this one in the first try. But the more I thought about it, the clearer it became. Also, the first approach of using prefixMax and suffixMax is great and can be used in other problems. All the best and keep improving.

[@MadirajuPhaniSaiSrinivas]

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

[@KrishnaSingh-rd6pr]

Dropping stack playlist in a queue Noice

[@souravmohanty834]

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

[@Aksht-h9u]

your reminder to revisit

[@Imtiyazbhai-ox9dg]

@@Aksht-h9u ++

[@arcane__1729]

+++

[@HarshKumar-mx9nj]

For those who cannot understand approach-2: According to the code of second approach given by striver there is mistake in dry run at 22:52 where he chose building of height 2 instead of 1 I think this was the mistake which made it difficult to understand approach 2

[@Diya-zb5xu]

it's stack and queue playlist and you are giving optimal solution of two pointer. way to go . atleast could have given the optimal stack use approach.

[@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

[@rushidesai2836]

The way you explained the second approach is commendable.

[@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♥

[@shikher4559]

Striver heap playlist is needed please!

[@killerboy2387]

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

[@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.

[@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 💌💌

[@apmotivationakashparmar722]

Thank you Striver for great explaination 😀🙏

[@premkulkarni7578]

class Solution { public: int trap(vector& nums) { int n = nums.size(); // 1st step vector prefixmax(n); prefixmax[0] = nums[0]; for (int i=1 ; i=0 ; i--){ suffixmax[i] = max(suffixmax[i+1] , nums[i]); } // 3rd final step int answer = 0; for (int i=0 ; i

[@hashcodez757]

bhai na toh stack use hua na hi queue 🥲😅

[@oyeshxrme]

optimal solution 🤐

[@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

[@swarupdas4114]

Optimal Solution 15:40

[@prathameshjadhav2942]

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

[@Sanyam7208]

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

[@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

[@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

[@AyanAbbas-ps8xv]

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

[@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

[@Ekam873]

@@zenmonk29 hi i believe my approach will not work bcz we nedd greatest on right not greater

[@Ekam873]

@@esmamanyt7048 hi i believe my approach will not work bcz we nedd greatest on right not greater

[@samiranroyy1700]

sir Understood Nice Explanation🥰🥰

[@chad._life]

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

[@kaichang8186]

understood, thanks for the perfect explanation

[@arnavjain6038]

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

[@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

[@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

[@sibiranganath]

why is this problem is under stack and queue playlist

[@KarumuriYasaswini]

optimal soln 😵

[@santoshkumarag727]

One quick question here, 1st approach pre computation(prefix/Suffix). 2nd approach two pointer. Why this has been tagged in stack or queue playlist. Any thoughts?

[@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

[@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;

[@Sridhar-fd5qr]

Dry run, you will understand the intuition

[@sauravfarkade1928]

Understood!! cout

[@godthunderbolt2190]

I tried to solve the Trapping Water -II with this approach but it failed on 19 test case Tell me where I am doing wrong class Solution { public: int trapRainWater(vector& heightMap) { // Here I have to see max for each side int m=heightMap.size(); // no of rows int n=heightMap[0].size(); // no of columns vectorleftrowwisemax(m,vector(n,0)); vectorrightrowwisemax(m,vector(n,0)); vectoruppercolwisemax(m,vector(n,0)); vectordowncolwisemax(m,vector(n,0)); for(int i=0;i

[@vamsikrishnagannamaneni912]

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

[@mayukhbhowmik934]

Bro Made stack question a two pointer question!!!

[@udaypaul77]

great explanation

[@MuraliSriramula-lm4zt]

where does stack used here?

[@mohanappriyakarunakaran]

Fine but where do we use stack ir queue here🤔

[@swadhinsahoo2846]

16:46 it has to be smaller not greater

[@gautamsaxena4647]

understood bhaiya

[@OmPrasad-x9u]

Nice Explanation

[@KartikeyTT]

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

[@yashverma2071]

Bhai tu padh na

[@vasuchourasia8021]

good question🥸

[@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

[@pranaymishra5456]

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

[@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

[@n5678--]

Isme stack queue ka use kahan hua??

[@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

[@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

[@aayush5474]

aadhe ghante ki video dekhli na stack use hua na queue

[@nikhiljain-nl7rs]

if condition is not needed in the last loop

[@aashikroy2198]

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

[@ddevarapaga5134]

Understood

[@lokesh8660]

How can we do it using just the suffix sum

[@shoaibaltaf1128]

By maintaining a variable that stores the leftmax and is updated while traversing from left to right

[@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

[@devireddysaikumarreddy4772]

Plse pop() this video from the stack playlist 😂

[@DeadPoolx1712]

UNDERSTOOD;

[@sanketatmaram]

understood!

[@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; } };

[@Bhargob_Lahon]

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

[@subee128]

Thanks

[@THOSHI-cn6hg]

two pointer approach is better

[@SapanaDashoni]

Definitely unable to make better approach at interview

[@AkOp-bf9vm]

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

[@JITESHSINGH-l7d]

Is it not a 2 pointer rather than stack 😂

[@KartikeyTT]

tysm sir

[@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

[@abhinavabhi3568]

Understood