Sum of Subarray Minimums | Detailed | Leetcode 907

Whatsapp Community Link : www.whatsapp.c...
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/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
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

[@varunbhargavmoori7815]

This is the only perfect video for this problem in the whole internet.

[@codestorywithMIK]

Thank you so much ❤️

[@lalitk]

Right 😊😊😊❤❤

[@sehajdhawan580]

Right I watched so many videos before coming to this due to its length 😅

[@technologicalvivek7510]

@@sehajdhawan580 Right

[@gui-codes]

agree

[@codestorywithMIK]

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

[@RaviTeja-cq6pu]

_, _, _, 2, _, _ how is it possible to start from 2. could you please explain.......

[@anuragv400]

@@RaviTeja-cq6pu take one scenario where you started and ended on 2.

[@fettuccine794]

This is the exact thing I was searching for in the entire internet, thank you So much ❤❤❤❤

[@10minutes_cs]

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)

[@Rajsingh-bh4qw]

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.

[@codestorywithMIK]

Thank you Raj 😇💕

[@bhuppidhamii]

when i did this Q's 3-4 weeks ago I fully understood it. but now today when i'm doing POTD I still cannot able to come back that stack will be used in this Q's. Why is it happening, what to do to prevent this?

[@codestorywithMIK]

Hi there, It happens with me also. Don’t worry. I usually either try it for 30 minutes, if I don’t get it, i watch the solution and try to figure what exactly i was missing. Remember one thing : For any qn, firstly try the worst solution- Brute Force, then go to optimal. It helps you understand what was the reason that was causing the high time complexity in brute force, what exactly we should improve to make it optimal. This helps a lot. And keep practising more and more.

[@bhuppidhamii]

@@codestorywithMIK thank you for your kind words

[@YashSinghal]

12:06 how did you think of this formula? I tried a lot to figure a similar formula

[@codestorywithMIK]

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

[@wearevacationuncoverers]

@@codestorywithMIK you are a magician

[@abhishekmittal1302]

Java Solution!!! class Solution { int[] getleft(int arr[], int n){ int res[] = new int[n]; Stack stk = new Stack(); for(int i=0;iarr[i]){ stk.pop(); } res[i] = stk.isEmpty()? -1 : stk.peek(); stk.push(i); } return res; } int[] getright(int arr[], int n){ int res[] = new int[n]; Stack stk = new Stack(); for(int i=n-1;i>=0;i--){ while(!stk.isEmpty() && arr[stk.peek()]>=arr[i]){ stk.pop(); } res[i] = stk.isEmpty()? n : stk.peek(); stk.push(i); } return res; } public int sumSubarrayMins(int[] arr) { int n = arr.length; int left[] = getleft(arr,n); int right[] = getright(arr,n); long sum = 0; long M = 1000000007L; for(int i = 0;i

[@harikuduva]

I don't even speak hindi and I understood your explanation more than those other videos explaining in english. Great work.

[@aws_handles]

😮😮😮

[@codestorywithMIK]

You made my day. Thank you so much ❤️❤️🙏🙏

[@footballcreativeeverywhere260]

East or west hindi is the best❤️😂

[@RajanSingh-xr7cf]

oh angrej ke chode ................ jyada gyan mt de bhai ko hindi aati ni haii ....

[@pranavkhatri30]

Till now, I have watched multiple videos for this concept. Couldn't find better explanation than this. Worth watching!

[@codestorywithMIK]

Thank you so much Pranav ❤️❤️❤️

[@Danish-saifi1]

You are creating a gold mine for future programmers ❤❤ loved the way of explanations Zero rote learning only concept ❤

[@codestorywithMIK]

Thank you so much ❤️

[@aryansinha1818]

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.

[@Newbie789]

bahut clear hai concept is video ke baad, thanks you so much. shaandar jabardust dindabaad😀

[@codestorywithMIK]

Thank you 😇🙏

[@sz.110]

*New Test cases Has Been Added* Overflow aaraha hai toh *long long* ka use karein

[@codestorywithMIK]

Thanks Sajjad ❤️❤️

[@nagmakhan672]

There is literally no video which gone to this depth for this Qn Thanks a lot 😊

[@harshitgupta8089]

Bhaiya I love you Your way of explaination is awesome I GOT THE BEST EXPLAINATION HERE FINALLY

[@codestorywithMIK]

Thank you so so much ❤️❤️

[@ramprasath3818]

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.

[@codestorywithMIK]

Thank you 😇🙏❤️

[@AMANRAJ-dt8gu]

The nicest explanation I have got as compared to other videos. Doing great job man🙏

[@aadil4236]

Very Good explanation brother. I was only able to get it after watching your explanation. Kudos to you!

[@souravjoshi2293]

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 ❣

[@codestorywithMIK]

This comment made my day. Thanks a lot ❤️❤️❤️

[@shikharmalik3787]

this guy got some great voice...every question feels easy after that///

[@shristisrivastava7054]

You always explain the logic so well. Hats off to you!

[@subhajitdey135]

Bhaiya how to figure out this edge case jaisa ki is question me, question solve karte time to ya edge case dimag me nhi aya.

[@deveshsharma-u2l]

thanks bro loved it !Thanks😘😘😘😘😘😍 Enjoyed it Dil de

[@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

[@rajubali5627]

super sir...this is perfect explanation......

[@rahuldwarijadavpuruniversi9322]

I'm confused about one thing sir - we are calculating how many times an element come out as minimum in different subarrays and then adding them by multiplying the element. But how do we conclude that this approach will cover all the subarrays ? I mean how they are equivalent ?

[@codestorywithMIK]

Let’s understand with an example. Suppose we write all the subarrays in which each element nums[i] is minimum. [17 , 55 , 82 , 55] Let's write for 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] Let's write for 55: [55], [55, 82], [55, 82, 55] -----> Keep an eye on this Let's write for 82 : [82] Let's write for 55 : [55], [82, 55], [55, 82, 55] ---> NOTE here [55, 82, 55] is duplicate when we wrote for last time 55 above. To avoid the duplicate I mentioned above. In one of the calculations, NSR or NSL, don't put >= So, for last 55, we will get [55], [82, 55] Now, start calculating : For 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] - 4 subarrays in which 17 is minimum so, result = 4*17 For 55: [55], [55, 82], [55, 82, 55] - 3 subarrays in which 55 is minimum result += 3*55 For 82 : [82] - 1 subarray in which 82 is minimum result += 1*82 For last 55 [55], [82, 55] - 2 unique subarrays in which this 55 is minimum result += 2*55 Total = 68 + 165 + 82 + 165 = 425 Hope this helps everyone. Thank you ❣

[@rahuldwarijadavpuruniversi9322]

@@codestorywithMIK Clear !! Thank you sir ❤

[@itssumit6161]

You are just awesome sir u made the question more easy with your explanation. ❤

[@shubhamagarwal8297]

duplicate case - [1,2,2] (makes us think)

[@codestorywithMIK]

Indeed

[@akshatmishra9574]

That Was Damn Clean and Good Explanation Bro !!

[@iayushsharma]

Thankyou Mik for awesome content

[@niteshk0487]

Bhai God Level explanation❤✅

[@codestorywithMIK]

Thanks a lot Nitesh ❤️❤️❤️

[@arthurlewin1952]

Amazing explaination sir solve largest rectangular area of histogram using this

[@codestorywithMIK]

Sure Arthur. Thanks a lot I will soon upload Histogram one

[@khitijkarmakar]

definitely not a medium , perfect hard problem.

[@Afiniciado]

best explanation found so far!!!

[@RajanSingh-xr7cf]

sach mai great explation _____________

[@bhuppidhamii]

corner case 35:35

[@SamsIt-hi9gf]

bhai your explaination is op....

[@it17harshahuja81]

Liked only because of the Edge Case👍👍👍👍

[@shadowgamer8105]

Sir love you dil se sachhi bole rahe hai aapke jaisa bhot kam log free mein intuition provide krta hai literally thank you sir 👌👌

[@dumbstonks]

Bhai don't ever stop uploading such detailed intuitive videos, these are like finding gems in a junkyard

[@medhanshagrawal5787]

Just Perfect Broo. Loved it❤

[@harshtiwari416]

Bhai aap keh rahe ho ki duplicate add hojayenge but agar test case [17 , 55 , 82 , 55] isko bina >= ke kru toh sum kum aarha hai 483 na ki zyada sahi answer se 593 kindly explain

[@codestorywithMIK]

The correct answer is 425. Let me explain how. First, write all the subarrays in which each element nums[i] is minimum. [17 , 55 , 82 , 55] Let's write for 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] Let's write for 55: [55], [55, 82], [55, 82, 55] -----> Keep an eye on this Let's write for 82 : [82] Let's write for 55 : [55], [82, 55], [55, 82, 55] ---> NOTE here [55, 82, 55] is duplicate when we wrote for 55 above. To avoid the duplicate I mentioned above. In one of the calculations, NSR or NSL, don't put >= So, for last 55, we will get [55], [82, 55] Now, start calculating : For 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] - 4 subarrays in which 17 is minimum so, result = 4*17 For 55: [55], [55, 82], [55, 82, 55] - 3 subarrays in which 55 is minimum result += 3*55 For 82 : [82] - 1 subarray in which 82 is minimum result += 1*82 For last 55 [55], [82, 55] - 2 unique subarrays in which this 55 is minimum result += 2*55 Total = 68 + 165 + 82 + 165 = 425 Hope this helps everyone. Thank you ❣

[@ritikabisht2055]

Really nice and detailed explanation ❤

[@robot3.077]

best explanation on youtube. fell in love with your explanation🙏🙏😍😍

[@codestorywithMIK]

🙏🙏❤️❤️

[@prathamtetgure2963]

Guys 50min jyada lagega dekhlo worth hai, dusri video dekhne ki jarurat nahi padegi

[@codestorywithMIK]

It means a lot 🙏😇❤️

[@subhamoysasmal8382]

sir you are simply great

[@Raj10185]

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.

[@codestorywithMIK]

indeed

[@MakeuPerfect]

You are superb

[@codestorywithMIK]

Thank you so much ❤️❤️❤️

[@dyashwanth9822]

Thank You so much bhai , Very well explained ❤

[@codestorywithMIK]

❤️🙏

[@Rajan-xv9cz]

genvin

[@nitingoel258]

Very well explanation !

[@ankitasantape1063]

Thanks a lot Sir for this wonderful in depth explanation.

[@codestorywithMIK]

You are most welcome 🙏

[@dayashankarlakhotia4943]

public int sumSubarrayMins(int[]arr){ int mod=1000000007; int[]st=new int[arr.length+1]; int idxSt=0; long ans=0; for(int i=1;i=0&&(i==arr.length||arr[st[idxSt]]>arr[i])){ int idx=st[idxSt--]; int leftIdx =idxSt

[@jagdishkhetre4515]

Thank you so much for detailed Explaination ...[ Formula :-> i - NSL[i] * NSR[i] - i ]

[@ankitgupta7467]

That's called a mindblowing explanation!!! Amazed at How I stayed here for 49 minutes, It was worthwhile.

[@parvahuja7618]

Thankyou so much sir

[@anveshasharma2726]

very nyc explaination. support from haryana

[@codestorywithMIK]

🙏🙏❤️❤️😊😊

[@akshitatyagi04]

Best Explaination!

[@jambajuice07]

left + 1 * right +1 how u thought of this ? i was doing something like left + right + left*right ( combination ) but got wrong answer

[@codestorywithMIK]

Actually i ran some examples before confirming the formula.

[@codestorywithMIK]

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

[@ss8273]

thank you sir keep it up really helpful........😍😍

[@codestorywithMIK]

Most welcome❤️❤️

[@footballcreativeeverywhere260]

Great mik bhai❤

[@pankaj_2003]

best explaination i hv got fr this question ,thankyou so much ........

[@Er0Shara]

nice explanation, always satisfying to see a solution coming from intuition. Thanks Mazhar. One small typo, i think while filling NSR via stack at time syamp kzbin.info/www/bejne/foO0c2pjeZeVn5I , I think at last instead of 3 , index 0 should be pushed in stack. But yeah question trick is quite confusing , but the ay to make it understand is really helpful, a lot of effort has been put in, in making this video they way it is, hence understandable with some typos.

[@tryin_to_code]

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

[@parassaini8601]

Hello Sir, could you please solve Range Module question!

[@newBieGuy05]

your explanation is awesome , I understood in one go,, It's better to watch one video of 50 minutes in detail rather than 5 to 6 videos of each 20 mins.

[@codestorywithMIK]

Thank you so much ❤️😇🙏

[@varunsheth1003]

Nice Explanation

[@shivamnirmalkar6251]

//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

[@i6757]

finding subarray and storing by brute force is O(n^3) how you are saying it is of O(n^2) @3:30 ?

[@Mohit-fe5hx]

Next APJ Abdul Kalam Sir

[@codestorywithMIK]

🙏🙏❤️❤️ Although I can never become like him The Legend. But I will definitely try my best to contribute to the coding community 🙏❤️😇

[@thestrangers6433]

Best on youtube ❤

[@dhruvaseri2082]

great work...

[@TejalKumawat-hu9yi]

best explaination on the internet for this question

[@codestorywithMIK]

Thank you ❤️

[@Kings-ik9lh]

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);

[@wearevacationuncoverers]

This is the only best explanation I found for this problem. You are too good. Let's support this Legend and make him famous.

[@alizhadigerov9599]

in 29:54 you are putting the value 3 inside the stack, but after that you are putting indices. Do we need to put indices into the stack or values?

[@this_is_ur_ms]

Great Explanation, cleared everything. Thankyou.

[@stroker01]

best!!!!!!!!!!!!

[@eng.gaming5557]

Perfection belongs to one and only Mazhar Khan Sir... Thanks for ur efforts

[@codestorywithMIK]

❤️❤️🙏🙏means a lot

[@stepup7052]

thanks bhaia

[@codestorywithMIK]

Glad i could help ❤️😇

[@hiteshkumaryadav8373]

Wo duplicate wala to clear kiya hi nhi bhai, bas seedha bta diya ki ek jagah equal to lga diya. Wo to maine bhi kr liya tha bhai 🙂

[@codestorywithMIK]

Apologies if you felt so. Take this for understanding - [17 , 55 , 82 , 55] Let me explain with an example. First, write all the subarrays in which each element nums[i] is minimum. [17 , 55 , 82 , 55] Let's write for 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] Let's write for 55: [55], [55, 82], [55, 82, 55] -----> Keep an eye on this Let's write for 82 : [82] Let's write for 55 : [55], [82, 55], [55, 82, 55] ---> NOTE here [55, 82, 55] is duplicate when we wrote for 55 above. To avoid the duplicate I mentioned above. In one of the calculations, NSR or NSL, don't put >= So, for last 55, we will get [55], [82, 55] Now, start calculating : For 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] - 4 subarrays in which 17 is minimum so, result = 4*17 For 55: [55], [55, 82], [55, 82, 55] - 3 subarrays in which 55 is minimum result += 3*55 For 82 : [82] - 1 subarray in which 82 is minimum result += 1*82 For last 55 [55], [82, 55] - 2 unique subarrays in which this 55 is minimum result += 2*55 Total = 68 + 165 + 82 + 165 = 425 Hope this helps everyone. Thank you ❣

[@hiteshkumaryadav8373]

@@codestorywithMIK thank you for the explanation

[@closer9689]

💯🙏 wow!!

[@adityatomar9820]

god level explanation bhaii...i was struggling so much in this ques

[@jayashankarmaddipoti6964]

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.

[@codestorywithMIK]

Definitely 💪💪💪 Keep going 🔥

[@souravsingh9993]

Thanks bro.

[@Siddharth1924]

top notch!!

[@jagadeeshp1163]

[71,55,82,55] why is this case giving me 703 instead of 503 def nsel(self,arr): n=len(arr) st=[] NSL=[-1 for i in range(n)] st=[0] for i in range(1,n): if arr[i]>arr[st[-1]]: NSL[i]=st[-1] st.append(i) else: while(st and arr[st[-1]]>=arr[i]): st.pop() if st: NSL[i]=st[-1] st.append(i) return NSL def nser(self,arr): n=len(arr) st=[] NSR=[n for i in range(n)] st=[n-1] for i in range(n-2,-1,-1): if arr[i]>=arr[st[-1]]: NSR[i]=st[-1] st.append(i) else: while(st and arr[st[-1]]>=arr[i]): st.pop() if st: NSR[i]=st[-1] st.append(i) return NSR def sumSubarrayMins(self, arr: List[int]) -> int: left=self.nsel(arr) right=self.nser(arr) cnt=0 for i in range(len(arr)): l=i-left[i] r=right[i]-i cnt+=(l)*(r)*arr[i] return cnt can some helpme out figuring the mistake i did ??

[@codestorywithMIK]

The correct answer is 425. Let me explain how. First, write all the subarrays in which each element nums[i] is minimum. [17 , 55 , 82 , 55] Let's write for 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] Let's write for 55: [55], [55, 82], [55, 82, 55] -----> Keep an eye on this Let's write for 82 : [82] Let's write for 55 : [55], [82, 55], [55, 82, 55] ---> NOTE here [55, 82, 55] is duplicate when we wrote for 55 above. To avoid the duplicate I mentioned above. In one of the calculations, NSR or NSL, don't put >= So, for last 55, we will get [55], [82, 55] Now, start calculating : For 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] - 4 subarrays in which 17 is minimum so, result = 4*17 For 55: [55], [55, 82], [55, 82, 55] - 3 subarrays in which 55 is minimum result += 3*55 For 82 : [82] - 1 subarray in which 82 is minimum result += 1*82 For last 55 [55], [82, 55] - 2 unique subarrays in which this 55 is minimum result += 2*55 Total = 68 + 165 + 82 + 165 = 425 Hope this helps everyone. Thank you ❣

[@codestorywithMIK]

This is one of the most critical corner case of this problem. Either in NSR or in NSL, replace >= check with > Any one of them.

[@jagadeeshp1163]

@@codestorywithMIK This question has lot of taught process needed to learn many things from this single question thanks for the tips thanks for the top level intuition behind this and thanks alot for the quick response

[@RV-qf1iz]

thanks bro i was able to solve this problem on my own after understanding the logic.

[@codestorywithMIK]

Glad to hear that 😇❤️🙏

[@harshtiwari416]

bhai zara aap brute force ki time complexity kaise n^3 hogyi explian kr skte hai????

[@codestorywithMIK]

My bad, a better Brute force also exists O(n^2) A better Brute Force : class Solution { public: int M = 1e9 + 7; int sumSubarrayMins(std::vector& arr) { int n = arr.size(); long result = 0; for (int i = 0; i < n; i++) { int minVal = arr[i]; for (int j = i; j < n; j++) { minVal = min(minVal, arr[j]); result = (result + minVal) % M; } } return result; } }; The time complexity of this brute-force approach is O(N^2) . In the worst case, you have to iterate through all N elements for both starting and ending indices.

[@harshtiwari416]

Bhai aap keh rahe ho ki duplicate add hojayenge but agar test case [17 , 55 , 82 , 55] isko bina >= ke kru toh sum kum aarha hai 483 na ki zyada sahi answer se 593 kindly explain

[@codestorywithMIK]

The correct answer is 425. Let me explain how. First, write all the subarrays in which each element nums[i] is minimum. [17 , 55 , 82 , 55] Let's write for 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] Let's write for 55: [55], [55, 82], [55, 82, 55] -----> Keep an eye on this Let's write for 82 : [82] Let's write for 55 : [55], [82, 55], [55, 82, 55] ---> NOTE here [55, 82, 55] is duplicate when we wrote for 55 above. To avoid the duplicate I mentioned above. In one of the calculations, NSR or NSL, don't put >= So, for last 55, we will get [55], [82, 55] Now, start calculating : For 17 : [17], [17, 55], [17, 55, 82], [17, 55, 82, 55] - 4 subarrays in which 17 is minimum so, result = 4*17 For 55: [55], [55, 82], [55, 82, 55] - 3 subarrays in which 55 is minimum result += 3*55 For 82 : [82] - 1 subarray in which 82 is minimum result += 1*82 For last 55 [55], [82, 55] - 2 unique subarrays in which this 55 is minimum result += 2*55 Total = 68 + 165 + 82 + 165 = 425 Hope this helps everyone. Thank you ❣

[@sabbulingineni]

Great video ❤ Pls do videos on solid principles and design patterns pls 🙏🙏🙏

[@aayushranjan5572]

bhai pls brute force wale sb ka v code bata do

[@codestorywithMIK]

A better Brute Force : class Solution { public: int M = 1e9 + 7; int sumSubarrayMins(std::vector& arr) { int n = arr.size(); long result = 0; for (int i = 0; i < n; i++) { int minVal = arr[i]; for (int j = i; j < n; j++) { minVal = min(minVal, arr[j]); result = (result + minVal) % M; } } return result; } }; The time complexity of this brute-force approach is O(N^2) . In the worst case, you have to iterate through all N elements for both starting and ending indices.

[@akworld2739]

bhai plese mera sirf duplicate wala concept clear nhi hua

[@gocrazy6177]

How can someone be so good at explaning logics ??

[@codestorywithMIK]

🙏🙏🙏❤️❤️❤️

[@gocrazy6177]

@@codestorywithMIK 🙏🙏🙏 bless me sir

[@k-CE-OmkarPathak]

op

[@shubhamkewat2496]

I Appreciate it.

[@codestorywithMIK]

Thanks a lot ❤️

[@Abhay14]

thanks a lot bhaiya , sayad hi aapse acchha koi iss question ko samjha skta tha this topic was so deep and interested

[@tusharyadav5874]

Great explanation bhai :)

[@codestorywithMIK]

Thanks 🙂

[@aadarshdontul5732]

Intuition.... is the main thing that way you have explained.

[@SurajKumar-ku1lg]

best video explanation of that problem

[@DR-mq1le]

great explanation! thanks

[@codestorywithMIK]

Glad it was helpful! 😇❤️

[@sjxsubham...]

best.... solution... thank MIK sir

[@sohamjoshi25]

Great Video!!!! Keep it up.

[@codestorywithMIK]

🙏🙏❤️❤️