907. Sum of Subarray Minimums | Monotonic Stack | Brute - Better - Optimal

[@ARYANMITTAL]

Don't know what LC smoked, before placing this Problem as Medium 🫠🫠

[@infinitysoundmotivation9768]

Weed 😢

[@gdivya1895]

This question ate my brain for the past two hours, I've tried all other videos available for this question, including big names like neetcode, but your solution is the only one that I could understand from start to finish. Well done sir. Earned a subscribe.

[@manwinsingh7381]

Same here

[@dhushyanthankannan8856]

This is the greatest explanation among all the explanations available in yt

[@madhubala5655]

Finally after watching the solution in 4 different channels I understood it here

[@mcw0805]

Thank you so much for explaining HOW the count works. I was trying to recall what I learned in my combinatorics class years ago lol

[@homeroserna9983]

Great solution. I like how you worked out the problem step by step completely before going to the code. You made a hard problem seem easy.

[@k.k.harjeeth5422]

24:06 this was brilliant !

[@gonuguntlakoushik899]

loved your way of explanation❤

[@jjjyotijain]

bro, what an amazing explanation. now I don't have any doubt left after watching this video. and now I can easily solve the problems of same pattern. Thank you very much for such a great explanation😍👏👏.

[@tejaschalke1778]

I was pissed I couldn't solve this problem but, now I feel a little better considering how hard this was. Also please make a video on KMP 😮‍💨, waiting from the previous weekly contest.

[@ARYANMITTAL]

That video is out bro, that day only it came - Write on yt - Kmp by Aryan Mittal, you will get the video ❤️❤️🫂

[@tejaschalke1778]

@@ARYANMITTAL damn i completely missed it 😅.

[@juliankuhn9742]

thank you this is the best explanation I found :)

[@saurabhchaudhari4157]

class Solution { private: vector prevSmaller(vector&arr){ int n=arr.size(); vectorans(n); stackst; for(int i=0;ielm){ st.pop(); } //empty if(st.empty()){ ans[i]=-1; } else{ ans[i]=st.top(); } st.push(i); } //push return ans; } vector nextSmaller(vector&arr){ int n=arr.size(); vectorans(n); stackst; for(int i=n-1;i>=0;i--){ int elm=arr[i]; //pop while(!st.empty() && arr[st.top()]>=elm){ st.pop(); } //empty if(st.empty()){ ans[i]=-1; } else{ ans[i]=st.top(); } //push st.push(i); } return ans; } public: int sumSubarrayMins(vector& arr) { int n=arr.size(); int MOD = 1000000007; vectornext=nextSmaller(arr); vectorprev=prevSmaller(arr);; long long sum=0; for(int i=0;i

[@sagarsaini5377]

finally a good explaination.

[@physicstyco8631]

amazing explanation bro

[@ohhpeejoshi9110]

thankyou so much buddy! very nice

[@mrityunjoybarman9098]

Actually I'm not good at hard problems but after reading the problem I don't know how it clicked my mind and cracked the monotonic stack solution.

[@k.satish3663]

totally understood ! thank you so much bro

[@codeman0017]

#include #include #include using namespace std; class Solution { public: int sumSubarrayMins(vector& arr) { stack st; vector next_lesser(arr.size(), arr.size()); vector prev_lesser(arr.size(), -1); for (int i = 0; i < arr.size(); i++) { while (!st.empty() && arr[st.top()] >= arr[i]) { next_lesser[st.top()] = i; st.pop(); } prev_lesser[i] = st.empty() ? -1 : st.top(); st.push(i); } long long answer = 0; double mod = 1e9 + 7; for (int i = 0; i < arr.size(); i++) { long long left = i - prev_lesser[i]; long long right = next_lesser[i] - i; answer += arr[i] * left * right; answer %= (long long)mod; } return (int)answer; } }; int main() { Solution sol; vector arr = {3, 1, 2, 4}; cout

[@lohithaadapala6989]

Excellent!

[@aa_maruf]

Brilliant explanation♥

[@janardhan2jordan]

I cant get a hold on why left*right works i get that it tells us that how many subarrays will include that particular number, but cant understand why it works?? anyone explain if possible, Great video by the way....Clear and precise.

[@kannank4269]

How aryan can maintain work n leetcode parallely

[@jaatharsh]

superb explanation, really like it (tired of python explanation :D)

[@mdsajidanwar6416]

Given constraint is 3x10^4 , then O(n^2) should work then why it's TLE showing

[@josephsamuelm4608]

Bro can u solve Sum of Subarray Ranges as well. Thanks in advance !

[@deepneurallearner]

Bhai aapne cnt ko tho badhaya hi nahi jab voh while loop main nahi ghus raha hai tab???

[@gaishurajput8239]

Showing TLE

[@aryansonwani7061]

did it by myself in half hour

[@aryansonwani7061]

stack st; st.push(-1); int n=arr.size(); vector dp(n); long long ans=0; for(int i=0;iarr[i-1]) dp[i]=(arr[i]+dp[i-1]); else { // 2nd case while(st.top()!=-1 and arr[i]

[@blackvelta1913]

bro can you explain it please

[@YashGulhane-uv9yf]

watched

[@gauristar4094]

thanksssss

[@AkashDeep-jp1ts]

Fucked up my mind!

[@samiranroyy1700]

🧡❤❤❤❤❤❤❤❤❤

[@ishanbhardwaj6082]

Correct me if I'm wrong, but I believe the code fails for brute and better. Because it is not taking into account single element subarrays. Thank you for the stack solution tho, I was stuck on it the whole day lol

[@abc-ym4zs]

bhaiya to improve logical thinking should i need to do cp bhaiya i am in third year i am not getting interest any tips bhaiya

[@veekykumar4211]

Why Wrong Answer Runtime: 7 ms Case 1 Case 2 Input arr = [11,81,94,43,3] Output 384 Expected 444 class Solution { public: int sumSubarrayMins(vector& arr) { int MOD = 1e9 + 7; int n = arr.size(); vector left(n,0), right(n,0); stacksLeft, sRight; for(int i=0;iarr[i]){ cnt+=sLeft.top().second; sLeft.pop(); } sLeft.push({arr[i],cnt}); left[i]=cnt; } for(int i=n-1;i>=0;i--){ int cnt=1; if(!sRight.empty() && sRight.top().first>=arr[i]){ cnt+=sRight.top().second; sRight.pop(); } sRight.push({arr[i],cnt}); right[i]=cnt; } long long sum = 0; for(int i=0;i