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 😭.
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
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.
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.🙏🙏🙏
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.
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
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 💌💌
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.
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
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
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!!🙌🏼☺
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?
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
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
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
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; } };
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
the prefix/suffix match approach is a lot better to understand imo
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 😭.
it's a DP apprach.
@@kulyashdahiya2529 how so, bro ?
CORRECTION->
22:51 we have to take the smaller one
yup exactly we will go with the smaller one.
yess
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
Yes I watched many times and thought to put this comment and found ur comment 😅
yeah bro
16:46, arr[i] has to be *smaller* than and NOT greater than leftMax and rightMax to store water on top of it
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❤❤😭
wrong problem to say this, barely anyone understood what he said in the second approach
Fr😂😂@@shreyxnsh.14 gotta see once more will see what I'm missing
@@shreyxnsh.14 well this problem is actually pretty hard to explain you will need to imagine the whats actually happening
Corrections in video :
16:46 & 22:51 - Take Smaller One*
Totally confused in the better approach!!😢I think the bruteforce approach is better..
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
better is cup cake
read my comment. you'll get the gist of it. 😇
@@farchit9467 what does llly mean dude?
@@vamsikrishnagannamaneni912 similarly
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.
Thanks a lot bro 🤗
with this single thought , I have implemented it easily .
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.🙏🙏🙏
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.
The optimal approach would definitely not strike in an interview if not revisited😂
your reminder to revisit
@@Aksht-h9u ++
+++
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
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.
The way you explained the second approach is commendable.
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 💌💌
Dropping stack playlist in a queue
Noice
Striver heap playlist is needed please!
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.
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♥
Striver we want Heap playlist its important in intership round there is question of heap
Optimal Solution 15:40
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.
bhai na toh stack use hua na hi queue
🥲😅
Why is this in stack and queue playlist? Shouldn't this be int the 2 pointer and Sliding window playlist??
exactly
But neither stack nor queue is used? 🤔🤔
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
@@Ekam873 can you explain more or share your code please
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
Thank you Striver for great explaination 😀🙏
22:57 l=1 and r=2 then why you choose r=2 we have to choose smaller one right ??
same doubt??
prolly mistake
a mistake we should take lmax = 1 here he did a typo, pls take a note of it
I strongly advise that if not understood Better Approach then Dry run of pseudo code..
optimal solution 🤐
but i just want to say your explanation is best out of all ............
sir Understood
Nice Explanation🥰🥰
Doubt
Ye pure process me stack kaha use hua jo ye stack ka topic ha
understood, thanks for the perfect explanation
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
i did the same.but code is a bit errenous. can u share the code please
my thought process was same but fucked up while writing code
@@zenmonk29 hi i believe my approach will not work bcz we nedd greatest on right not greater
@@esmamanyt7048 hi i believe my approach will not work bcz we nedd greatest on right not greater
Amazing optimal solution
Aree dhano 😅
Optimal samjh aa gaye be ???? Aate h room pe
16:46 it has to be smaller not greater
thanks u bhaiya for this quality content
for the very first time solved a hard problem in a single go
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;
arr[i] has to be strictly less than leftmax and rightmax this is the correction folks pls take care of.
Yes. He mistakenly said greater
Dry run, you will understand the intuition
Bro Made stack question a two pointer question!!!
why is this problem is under stack and queue playlist
Please link problem on code 360 in description. Great Video as always!
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!!🙌🏼☺
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
great explanation
optimal soln 😵
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?
Nice Explanation
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
Understood!!
cout
Why are we incrementing the smaller one in O(1) SC approach?
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
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
understood bhaiya
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
ye stack and queue ka question to nhi h fir is playlist me kyu h
Bhai tu padh na
good question🥸
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
I thought he would explain the approach by using stack as well.
if condition is not needed in the last loop
aadhe ghante ki video dekhli na stack use hua na queue
Fine but where do we use stack ir queue here🤔
why this video is in stack and queue playlist?
There is no use of stack or queue
stack toh use hi nhi ho rha , toh stack playlist me kiu h ye
where does stack used here?
Isme stack queue ka use kahan hua??
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
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
second approach is better
for vectors use pass by reference
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;
}
};
Why traversing the smaller one someone can tell .?
if you traverse the greater one, how can you store the water? draw a curve for the array and think....you will understand!
i will look like a container
@@dhruvkhanna2410 thanks bro for the help
Plse pop() this video from the stack playlist 😂
Why in l and r we always choose smaller building?
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
Definitely unable to make better approach at interview
How can we do it using just the suffix sum
By maintaining a variable that stores the leftmax and is updated while traversing from left to right
i have a question ... we done both approach without stack then why this question is in stack playlist??
two pointer approach is better
UNDERSTOOD;
Is it not a 2 pointer rather than stack 😂
Understood
understood!
Thanks
tysm sir
Please review the video before releasing it, as every video usually contains at least one mistake
daam man
Why this question is marked as hard on leetcode??
because its hard man :) prolly due to the optimal approach
explanation is not too good , begineer will never git it.
thanks
Understood
Understood
Understood