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/
@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!!
*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 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)
@@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]);
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 😄😂
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 ^_^
@@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 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.
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 u are not cheating :) even the interviewer knows you have prepared from leetcode. No one expects you to come without preparing so chill out.
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
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.♥️
@@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 :)
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.!!!!
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??
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
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.
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 ?
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
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--){
@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 ?
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 ?
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.
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 ??
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)
please try to explain why and how to reach to a particular approach rather than jumping to the code and explaining via the code. I am just finding it difficult to understand .
Brute better were there to understand the approqch, and the two pointer without code on side will become complicated to explain. Try explaining once, you will understand :) Bdw watch the last part to understand the intuition..
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
Don't you think it is better to explain the Intuition before explaining the optimal algorithm? You will create the algorithm only after you have the intuition then why not explain it before so it becomes easy for us to understand as well? Just curious.
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/
@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!!
Seriously wanted this video , thanks bhaiya 😘😘😘😌😌😌
great work you have been working real hard for us
Understood it well.
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*
can you please share a useful link for learning prefix max and suffix max ? i would be thankful
@@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)
exactly
@@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]);
@@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.
ye to mujhe pata hi nahi tha lol.
Video explanations bhai ka best hai plus voice m jo energy hai na wo jagaa k rkhti h
bhai love babbarne laya tha pehle
@@pranaykumar9433 na bhai date dekh lo dono videos k
Bhaiya word wrap question pr ek video bnaiye plz
I feel intuition should precede the algorithm always. That's where the skill of problem-solving comes in.
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 😄😂
XD
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 ^_^
took me 2 times to understand intuition but this is best video you can get on this problem , good work .
That optimized explaination with intuition went directly inside my head. Thank you brother 👍
Perfect!
can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?
is this solution under DP ? if yes then why is it under DP ?
@@freshcontent3729 th-cam.com/video/XngqZTQcQ3E/w-d-xo.html&ab_channel=ClubofProgrammers%2CIITBHUVaranasi
@@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...
Why are we checking whether a[l]< a[r]? Isn't it more intuitive to check whether leftMax
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
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.
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
9:22 most optimal solution
16:22 intuition
You are the most effective teacher and I am immensely grateful for your work.
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.
that intuition that you explained at the end cleared all my doubts and got me a solid understanding! perfect 🥳
the last approach explanation was amazing. Thank you so much brother. :)
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.
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.
@@takeUforward it's the fear of getting caught. Thanks btw. : )
@@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.
@@takeUforward Oh.. I didn't know that side.. If that's what it is, then no need to worry. Thanks Raj bro : )
@@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
GOD LEVEL EXPLAINATION!
whenever i stuck in a problem i search if u have made any video on that...love u
This is a great explanation with patience ! Thank you for sharing .
We can always increase l and r when the height[l]
Like omg the optimal solution explanation is of next level
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
did you get any answer?
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.
This is the best explanation I can ever find on yt for this problem... respect++;
I got the intuition when you explained the left pointer shifting. Did the rest by myself. Thank you for the video.
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.♥️
Hi Raj,
Can you please explain about this problem "Interleaving Strings "
I came here only to revise the two pointer method. Time stamps will be very helpful.
Understood....Thank You So Much for this wonderful video..................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Solutions and intuition are crystal clear as always bro
All the best!
@@manavmohata1240 Thanks bro
All the best for you too :)
did you got placed
@@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 :)
@@kage-musha1702 All the best buddy , keep going and stay healthy
Great Explanation!
The way u emphasize on the intuition makes it easy to grasp it.
is this solution under DP ? if yes then why is it under DP ?
you are for sure the best teacher India has ever seen !
😀
just saw the first 7 min and tried on my own..
and i solved it..
thanks..striver.
One request, it will we very helpful if you add timestamp for each approach.
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.!!!!
That's the awesome solution. Thanks a lot Striver💓
this is the best explanation available on youtube for this problem .👌👌👍😲
How does the optimized logic give correct answer for a sorted array ?
if the array is sorted , water will drain to the bottom.
Really so helpful to understand better.. Thanks for sharing🎉
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??
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
Sir hats off to you for the optimal solution. Also wishing you a speedy recovery
is this solution under DP ? if yes then why is it under DP ?
7:15 what is prefix and suffix here?
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.
Global audience is the main target .. I guess
Thanks a lot bro. So nice explanation..❤
Simply beautiful✨✨ Thanks!
is this solution under DP ? if yes then why is it under DP ?
@@freshcontent3729 no it's not DP
@@prakharagarwal6237 then how can we do it using dp ?
Thank you Dada for your efforts !
Hey, I got the logic of solving the problem like when a[r]
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.
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 ?
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
is this solution under DP ? if yes then why is it under DP ?
how to compute the prefix max and suff max??
use long long for storing ans if u r getting error
Brute force approach:
class Solution {
public:
int trap(vector& height) {
int ans=0;
for(auto i=0;i
can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?
2 pointer solution is mind blowing
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
wonderful explanation, you explained it so easily, thanks striver🙂🙂
very well xplained bro.I got the intuition
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]
Ye video 20 Dec 2020 ki hai and Love bhaiya ki 14 Oct 2020 ki hai. Iska matlab unki sheet pehle aayi thi
Such a great explanation...thanks a lot.
Striver's explanation is always perfect :)
finally i understood thanks a lot !!
Thank You Striver For this awesome Sheet
Bhya, explanation is too good, understood 💥💥💯
Thank You Sir. Bahot mast samjhaate hain. Aap🔥
Bhai mjaa aa gya .... Kya samjhaya hain.... Tumhare videos litreally above expectation hote hain...Majaa AA gya striver bhai
is this solution under DP ? if yes then why is it under DP ?
@@freshcontent3729 no it's not under dp
@@sourabhsisodia9563 then how can i do it using dp ?
@@freshcontent3729 i am just a beginner... Not started learning dp yet....If you want to know then just google it
Code provided in the discription giving wrong answer!
can't thank you enough for such superb explanation
Thank you striver
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
@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 ?
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!
@@takeUforward but bhaiya what if there is a time limit? Like if the interview is for 1 hour only?
@@takeUforward thanks bhai!!!
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 ?
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.
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 ??
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
Thanks!
solutions:
*BRUTE FORCE*
int maximum(vector height,int start,int end){
int max=INT_MIN;
for(int i=start;imax)
max=height[i];
}
return max;
}
int trap(vector& height) {
int ans=0;
for(int i=0;imax){
max=i;
preM.push_back(max);
}
else
preM.push_back(max);
}
max=INT_MIN;
for(int i=height.size()-1;i>=0;i--){
if(height[i]>max){
max=height[i];
sufM.push_back(max);
}
else
sufM.push_back(max);
}
reverse(sufM.begin(),sufM.end());
int ans=0;
for(int i=0;i
he is telling solution like gospel truths for life problems
This is Great Explanation
thank you
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)
you can watch anuj bhaiya video on 2nd approach, search tapping rainwater problem on youtube.
How do they think of such a great logic?...
What if it is 3,0,1
The code is there, just put some cout statements and you will get how the loops runs
Very Good Explanation👏👏👏👏👏👏👏
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...
can you please tell me how to write code to find the prefix and suffix array discuseed in this video ?
please try to explain why and how to reach to a particular approach rather than jumping to the code and explaining via the code. I am just finding it difficult to understand .
Brute better were there to understand the approqch, and the two pointer without code on side will become complicated to explain. Try explaining once, you will understand :) Bdw watch the last part to understand the intuition..
Bhaiya ye intership kis month, kis time ati h or website pe kaise or kaha dekhe or apply kaise kare..... Please please bata do
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
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
You are just teaching how to memorise the solutions.
Extremely well explained!!! :))))
Don't you think it is better to explain the Intuition before explaining the optimal algorithm? You will create the algorithm only after you have the intuition then why not explain it before so it becomes easy for us to understand as well? Just curious.
Usually people get confused as they cannot relate.
Very good explanation
7:20 Went through half the sde sheet understanding everything and bro said you shouldn't do it :(
Thank you very much sir.
Optimal solution from 8.50
You are great man🤗may your all dreams come true😍🙌
Bhaiya kya aap CodeForces and CodeChef ke solutions ke upar regular video bna sktey ho kya ?
Really recommend watching this video at 1x speed.
i didnt udnerstand this explanation. please include sub titles.
Beautiful video sir