Leetcode 907 Sum of Subarray Minimums | Monotonic Stacks | Coding Decoded SDE Sheet

[@CodeWithSunchitDudeja]

Coding Decoded Monotic stack : docs.google.com/spreadsheets/d/1iyTY-BltHISj5bK2IFETPLhjbJdi-TrWeLXAyH0JQTI/edit#gid=0

[@YashTyagi-c9k]

so awesome so amazing sunchit sir you are the best

[@paragroy5359]

Great Content. Keep on making such videos.

[@CodeWithSunchitDudeja]

I will try my best

[@jeffj97]

your organization is absolutely incredible. thank you so much!

[@sagarbora7768]

Congrats Guruji on 14k organic growth

[@CodeWithSunchitDudeja]

Thanks Sagar

[@aryangupta8952]

learnt a new concept of monotonic stack thanks man!

[@manjeetyadav5830]

when we see number of minimum elements left or right from an index . Do we count the curr index as one among them

[@chippapruthvi2773]

+1

[@hemu2723]

you are really very amazing

[@CodeWithSunchitDudeja]

Wow, thank you

[@tanson86]

Hey Sunchit, When you get time can you reorganise the directory structure in git, introducing a directory for year can make navigation more easy. Not sure if it is an easy task but think about it... An example would be /2022/November/(*.java | *.cpp etc). Is the solution of this problem in GIT? I don't see it.

[@CodeWithSunchitDudeja]

+1 to that, I wanted to do it long it back. but then realised that I have to update all the solution links of the videos released so far. Will make it more organised from 2023.

[@pwnweb5734]

very well explained

[@krateskim4169]

awesome

[@suryanshsinghchauhan5750]

Another approach using 1 stack and 1 dp array class Solution { public: int sumSubarrayMins(vector& arr) { stacks; int n=arr.size(); vectordp(n,0); int pre=-1; long long ans=0; int mod=1e9+7; for(int i=0;i=arr[i]){ s.pop(); } else break; } if(!s.size())pre=-1; else pre=s.top(); s.push(i); if(pre==-1){ dp[i]=((i+1)*arr[i])%mod; } else { dp[i]=(dp[pre]+((i-pre)*arr[i])%mod)%mod; } ans=(ans+dp[i])%mod; } return ans; } };

[@manasideshmukh737]

can you plz explain why you did this dp[i]=((i+1)*arr[i])%mod;

[@suryanshsinghchauhan5750]

@@manasideshmukh737 if we are at an index whose element is the smallest till that index starting from left, then all the subarrays ending at that index will have the minimum element equal to that smallest element and to compute dp[i] which contains the sum of minimum of all the subarrays ending at 'i' I performed (i+1)*arr[I] where (i+1) represents the number of subarrays and arr[i] is the minimum element.

[@suryanshsinghchauhan5750]

@@manasideshmukh737 hope this will help you.

[@manasideshmukh737]

@@suryanshsinghchauhan5750 understood...Thank you

[@alphadrones23]

why for rightMin the condition for pop is >= and for leftMin the condition is > ?

[@RajatGupta-vu8xp]

For equal condition, u can include that element either in left part or in right part, because it cant be in both .

[@fnGamingz]

1L 38k mails as unread 😀

[@devendrabhuarya4917]

Your solution not pass all test cases

[@DheerajKumarBarnwal]

make your description space useful for others. Put relevant information in the first part like question link, solution link, reference video link or any document(which you are mentioning in the video). Just look at the description part yourself, its full of garbage. Its cluttered.

[@CodeWithSunchitDudeja]

Thanks for such an honest feedback. Will work on it.