Sum of Subarray Minimums | Detailed | Leetcode 907
Vložit
- čas přidán 24. 11. 2022
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 4th Video of our Playlist "Stack : Popular Interview Problems".
In this video we will try to solve a very good and famous stack problem - Sum of Subarray Minimums (Leetcode 907)
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Sum of Subarray Minimums (Leetcode 907)
Company Tags : Paytm
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/sum-of-...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach Summary : The approach involves finding the next smaller element to the left (NSL) and the next smaller element to the right (NSR) for each element in the array. It utilizes a stack-based approach to efficiently compute these values.
The algorithm then iterates through each element of the array, calculating the distance to the nearest smaller element on the left (d1) and the distance to the nearest smaller element on the right (d2). For each element, it determines the total number of ways to form subarrays with that element as the minimum by multiplying d1 and d2. The sum of the minimum elements for each subarray is accumulated, and the result is returned after taking the modulo operation with 1e9 + 7.
The code leverages the concept of finding the next smaller element to efficiently compute the sum of minimum elements for all possible subarrays in a given array.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear
This is the only perfect video for this problem in the whole internet.
Thank you so much ❤️
Right 😊😊😊❤❤
Right I watched so many videos before coming to this due to its length 😅
@@sehajdhawan580 Right
agree
Sir love you dil se sachhi bole rahe hai aapke jaisa bhot kam log free mein intuition provide krta hai literally thank you sir 👌👌
I don't even speak hindi and I understood your explanation more than those other videos explaining in english. Great work.
😮😮😮
You made my day.
Thank you so much ❤️❤️🙏🙏
East or west hindi is the best❤️😂
Man who are you, "Best explainer I guess". How can you explain so good. Hats off to you. Thank you from bottom of my heart. Love and respect always. It felt like I am binge watching Netflix. It was that smooth and crisp and clear.
There is literally no video which gone to this depth for this Qn
Thanks a lot 😊
literally i watched so many videos but couldnt find a better explanation than this one. Thanks a lot sir🙏🙏🙏 each and every doubt is clear and also the edge cases.
Thank you Raj 😇💕
If you are wondering how we come up with the formula at 12:06 -
Let's take an example shown below :
_, _, _, 2, _, _
If you notice-
No. of ways to start our subarray from left of 2 (including 2) is = 4 (i.e. we have 4 possible starting points)
No. of ways to end our subarray at right of 2 (including 2) is = 3 (i.e. we have 3 possible endings for our subarray)
As per above two equations, For each starting point we have 3 ending points possible
Total = 4*3 = 12
_, _, _, 2, _, _
how is it possible to start from 2. could you please explain.......
@@RaviTeja-cq6pu take one scenario where you started and ended on 2.
This is the exact thing I was searching for in the entire internet, thank you So much ❤❤❤❤
still if u find it confusing , here is simple derivation.
let the number of elements before given element (eg: 2) be "b", and after given element (eg: 2) be "a",
so , total number of subarray will be
b // [3,4,5, 2] , [4,,5,2] , [5,2]
a // [2,3,4], [2,3]
1 // [2]
b*a // 9:07 cases
so equation is b + a + 1 + (b*a) .. if u solve this its equal to (b+1)*(a+1)
Till now, I have watched multiple videos for this concept. Couldn't find better explanation than this. Worth watching!
Thank you so much Pranav ❤️❤️❤️
bahut clear hai concept is video ke baad, thanks you so much. shaandar jabardust dindabaad😀
Thank you 😇🙏
This channel is gold. The way he explains it step by step by walking through what he thinks, is really great. And I don't even know Hindi lol. Thanks a lot.
Thank you 😇🙏❤️
Bekar hi itne videos dekhe. Pehle hi is channel me ajana chaie tha.
Bhai tumse acha isko koi nahi explain kar sakta. hats off to you
Intuition.... is the main thing that way you have explained.
Very Good explanation brother. I was only able to get it after watching your explanation. Kudos to you!
You are creating a gold mine for future programmers ❤❤ loved the way of explanations
Zero rote learning only concept ❤
Thank you so much ❤️
Bhaiya I love you Your way of explaination is awesome
I GOT THE BEST EXPLAINATION HERE FINALLY
Thank you so so much ❤️❤️
That's called a mindblowing explanation!!!
Amazed at How I stayed here for 49 minutes, It was worthwhile.
mene 3,4 videos dekhe youtube pe iss question ka point of view samajhne ke liye but ek bhi youtuber depth me bata nhi paye ,jis depth me aapne bataya.
Thank you.
❤️🙏
You are just awesome sir u made the question more easy with your explanation. ❤
Great Explanation, cleared everything. Thankyou.
Bhai God Level explanation❤✅
Thanks a lot Nitesh ❤️❤️❤️
First , your voice just makes me feel that the Qn is too easy and the way you explain , everything seems so effortless.I am still speechless with the amount of effort you put in a video. Thanks and congratulations for being such an impactful tutor. I can sense of urge in your voice to transfer the knowledge to us.
People will soon start knowing you from this channel.
Thanks from me and my friends in college who have started following you
❣
This comment made my day. Thanks a lot ❤️❤️❤️
this guy got some great voice...every question feels easy after that///
This is the only best explanation I found for this problem. You are too good.
Let's support this Legend and make him famous.
Best Explanation for this problem!! Thanks Sir : )
Nice Explanation
Such a detailed explanation! Hats Off 🔥🔥 Earned a subscriber!
Great content as usual. Whenever i search any question and notice that you have made a video on that, i immediately click on it without a second doubt , no matter how long the video. Please don't stop making and uploading such videos! You truly are a gem! Thank you sm!
Thank you so much.
Means a lot to me 😇🙏
Now I finally subscribed your channel after this great explanation👍.Really impressed with the way you explain this problem easily
Amazing explaination sir solve largest rectangular area of histogram using this
Sure Arthur.
Thanks a lot
I will soon upload Histogram one
You are superb
Thank you so much ❤️❤️❤️
Beautiful explanation. Was able to code myself after your explanation itself thanks !
You are absolutely right, others have directly written the code w/o proper explaination!! Thanks a lot Mik Bhai for this wonderful video
Thank you so much 😇❤️🙏🙏
best explaination i hv got fr this question ,thankyou so much ........
Literally, amazed by the way you elaborate on the solution.
Means a lot
Thank you 😇❤️
thanks a lot bhaiya , sayad hi aapse acchha koi iss question ko samjha skta tha this topic was so deep and interested
best explanation on youtube.
fell in love with your explanation🙏🙏😍😍
🙏🙏❤️❤️
Thank you so much sir, now i got the intuition.
One of the best explanations
By Far the best Explanation in CZcams !
It means a lot. Thank you so much 🙏😇
No one, I repeat no one can teach like this LEGEND
Best Explaination!
what a detailed explanation!!! ❤
Great mik bhai❤
best video explanation of that problem
Best Explaination!!
Subscribed❤. Loved the explanation.
Thank you so much ❤️❤️🙏🙏
Just Perfect Broo.
Loved it❤
love you sir ...finally abb samajh aaya
Liked only because of the Edge Case👍👍👍👍
Very well explanation !
Perfection belongs to one and only Mazhar Khan Sir...
Thanks for ur efforts
❤️❤️🙏🙏means a lot
Thankyou Mik for awesome content
god level explanation bhaii...i was struggling so much in this ques
Thank you so much MIK bhai 🙌
best explaination on the internet for this question
Thank you ❤️
Thanks a lot Sir for this wonderful in depth explanation.
You are most welcome 🙏
Best on youtube ❤
Really nice and detailed explanation ❤
best.... solution... thank MIK sir
Thanks bro.
very nyc explaination. support from haryana
🙏🙏❤️❤️😊😊
top notch!!
Wow! Thank you so much!!
You're welcome! 🙏😇
thanks bhai best explanation. on yt
bhai your explaination is op....
U are a genius..keep making videos for such lesser known problems
It means a lot 🙏🙏❤️❤️😇😇
Sure I will be posting more
good explanation brother thanks
I search all over internet for those videos which have brute force solution .....and after that i found this channel and here only i got step by step thinking towards optimal solution ............near about 60 days i follow this channel and explainations are really great
Means a lot ❤️❤️🙏🙏
Means a lot ❤️❤️🙏🙏
That Was Damn Clean and Good Explanation Bro !!
great explanation! thanks
Glad it was helpful! 😇❤️
beautifully explained, solved the sum of subarray ranges question by this method, keep up the good work
Thank you so much 😇❤️🙏
Thankyou so much sir
Probably the only video which is able to actually explain the intuition behind this problem.
❤️❤️🙏🏻🙏🏻
Dope explanation
Best one on internet 🔥
As usual, I was able to solve using a brute force approach and received a time limit exceeded error. No one born with enormous reasoning/analytical skills so as I. No need to worry, check who else solved the problem before, understand the approach and follow it. There is no mistake in following others when you are not sure. Thanks, MIK bro. No stop to learning. One day, I will become a pro of programming.
Definitely 💪💪💪
Keep going 🔥
This question is really amazing bas observation jaise kiya nsl and nsr se ho jyega bas question is very much standard bas formula figure out me thoda dikkat hua baki ab sab smoothly solve ho gya.
indeed
very well and thoroughly explained, Thank you for this
Thank you so much 😇❤️
thanks bhaia
Glad i could help ❤️😇
//vector getNSL(vector& arr, int n) , bhaiya aapne yaha NSL likh rakha hai or aap for loop se travel kr rhe right side //for(int i = 0; i
awesome exlaination after striver you are the best tutor on youtube for dsa.
❤️🙏
Thank You so much bhai , Very well explained ❤
❤️🙏
12:06 how did you think of this formula? I tried a lot to figure a similar formula
Let's take an example shown below :
_, _, _, 2, _, _
If you notice-
No. of ways to start our subarray from left of 2 (including 2) is = 4 (i.e. we have 4 possible starting points)
No. of ways to end our subarray at right of 2 (including 2) is = 3 (i.e. we have 3 possible endings for our subarray)
As per above two equations, For each starting point we have 3 ending points possible
Total = 4*3 = 12
@@codestorywithMIK you are a magician
very clear explanation for each and every point of the problem...bhaiya your explanation is crystal clear ,like no need to go for any other videos for understanding the concept after watching your video.
Means a lot. ☺
Very beautiful explanation and much intuitive thanks
You're most welcome 😇
we can also check left and right elements at the travrsal time of index also but it will take Time complexity O(N^2) but space complexity will be O(1)
int mod = 1e9 + 7;
int sumSubarrayMins(vector& arr) {
long long ans = 0;
for(int i=0;i=0 && arr[j]>=temp){
leftcount++;
j--;
}
int k = i + 1;
long long rightcount = 0;
while(ktemp){
rightcount++;
k++;
}
ans=(ans%mod+(leftcount+1)%mod*(rightcount+1)%mod*temp%mod)%mod;
}
return (ans % mod);
thank you sir keep it up really helpful........😍😍
Most welcome❤️❤️
Great Video!!!! Keep it up.
🙏🙏❤️❤️
Great explanation....
Thank you so much 😊
bahut E badhiya
thanks bro loved it !Thanks😘😘😘😘😘😍 Enjoyed it Dil de
I Appreciate it.
Thanks a lot ❤️
thanks bro i was able to solve this problem on my own after understanding the logic.
Glad to hear that 😇❤️🙏
Thanks a lot bhaiya ❣️ this was the best explanation for this question among all of the other explanations I have seen so far
Most welcome 😊
Great explanation bhai :)
Thanks 🙂
I tried to do this question using Sliding Window technique and following is the code that I have written :
class Solution {
public:
int sumSubarrayMins(vector& arr) {
vector result;
deque deq;
int n = arr.size();
int k = 1;
while(k
very nice
Great explanation ❤
❤️❤️🙏🙏
SImply awesome !!
Thanks a lot! 🙏😇
Today’s upload will be a little delayed because I am travelling. But I have provided the link of my GitHub code (exact copy of LCS code pattern) in my post in CZcams
Thank you 🙏😇
awesome exolanation !!!
Thanks a lot Manoj ❤️
You are gem 💎 brother
❤️❤️🙏🙏
Great video ❤
Pls do videos on solid principles and design patterns pls 🙏🙏🙏