L9. Sum of Subarray Minimum | Stack and Queue Playlist

[@kamalesh4904]

I've watched many videos on this topic, gave up on this question, and stopped solving problems for a few days, thinking that I'm so stupid. But this video gave a really clean picture in how to solve the problem Thank you so much for this video.

[@rushidesai2836]

Tutor matters :)

[@omkarshendge5438]

went complete blank after 20th minute man! very diffcult to understan this stack method

[@shikher4559]

watch the previous videos of next smaller / previous smaller, he has explained in detail

[@Hemanthkumar-ck1zu]

I think I have not studied high school properly 🥲🥲🥲

[@srivijaykalki4279]

For those who are still figuring out why there are 12 sub-arrays, Here is the quick and easy understanding. Here is the array after trimming : 4,6,7,3,7,8 (len : 6). What do we want to find? - Total number of sub-arrays that include 3. To get that lets split this into multiple subproblems: if if sub array starts from 4 and 3 included - we have 3 ways.they are : 4,6,7,3 4,6,7,3,7 4,6,7,3,7,8 simillary the sub array may start at 6 and 3 also included. then again we have 3 ways. they are : 6,7,3 6,7,3,7 6,7,3,7,8 similarly the sub-array can also start with 7, 3. which results in another 6 ways. Totally 12 (3 + 3 + 3 + 3) ways.

[@charchitagarwal589]

Thanks bro

[@devgupta9469]

How did it arrive to the multiplication part directly in video ?

[@souvik33and37]

Edge case handling: Make either one of PSE/NSE strictly smaller and other one smaller or equal to

[@laharianegama5004]

the edge case will be the death of me

[@mrmehran879]

c++ code for leetcode question. class Solution { public: int mod= 1e9+7; vector prev_smaller_equal_element_index(vector& arr, int n) { vector ans(n,0); stack st; for(int i=0 ; i arr[i]) // don't take >= as we have to consider for smaller equal element also eg [1,1,1] { st.pop(); } ans[i] = st.empty()? -1: st.top(); st.push(i); } return ans; } vector next_smaller_element_index(vector& arr, int n) { vector ans(n,0); stack st; for(int i=n-1 ; i>=0 ; i--) { while(!st.empty() && arr[st.top()]>= arr[i]) { st.pop(); } ans[i] = st.empty()? n: st.top(); st.push(i); } return ans; } int sumSubarrayMins(vector& arr) { int n = arr.size(); vector prev(n); vector next(n); prev= prev_smaller_equal_element_index(arr,n); // used to store the index of the previous smallest element; next= next_smaller_element_index(arr,n); // for(auto it: prev) cout

[@aryasharma69]

The better approach is actually very hard to understand but after watching the video 3 times i understood it.

[@apmotivationakashparmar722]

Thank you for such a great explaination . Edge Case needs to be remembered in this question.

[@hiraljhaveri3830]

Here only contiguous subarrays are considered. Also, it is assumed that there can be duplicates in the construction of such subarrays: E.g.: with input [1, 1], if you were to take distinct subarrays, there would be only 2, which are: [1] and [1, 1]. That gives sum = 2. But here 3 subarrays are considered: [1], [1, 1] and [1]. The first and last subarray are same in terms of their value, however they belong to different indices selection of the original array (i.e. first subarray is index 0 of original array, whereas third subarray is index 1 of original array). Hence expected sum/answer = 3. It would be better to explicitly clarify such assumptions.

[@darkistheknight]

Man, thnxs a lot. I was waiting eagerly for your Stack & Queues playlist. Thnxs a lot man.

[@Akshay-lf8dq]

4:56 Why tf is interviewer always unhappy

[@rajibdas5574]

Then ask him to solve it by his own. XD

[@santasanthosh2113]

@@rajibdas5574 real

[@aryanikale7187]

When they don't want to hire you this question comes up in the interview

[@Shivam-Jhaa]

Thanks Striver Bhaiya ❣️

[@RahulUnscripted_]

got it after watching it 3 times........

[@debapriyo007]

#Java_solution:[LeetCode] ✅ class Solution extends HelperMethod{ // inherit the class public int sumSubarrayMins(int[] arr) { HelperMethod help = new HelperMethod(); // object of helper fun to access the method. int[] nextSE = help.nextSmaller(arr); int[] prevSE = help.previousSmaller(arr); long total = 0; int mod = (int)(1e9+7); for (int i = 0; i < arr.length; i++) { int left = i - prevSE[i]; int right = nextSE[i] - i; total = (total + (long)left * right * arr[i]) % mod; } return (int) total; } } //purpose of creating another class just coz of organized the code.. class HelperMethod{ // Find the next smaller element public int[] nextSmaller(int[] arr) { int n = arr.length; int[] nse = 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(); } nse[i] = (stk.isEmpty()) ? n : stk.peek(); stk.push(i); } return nse; } // Find the previous smaller element public int[] previousSmaller(int[] arr) { int n = arr.length; int[] pse = new int[n]; Stack stk = new Stack(); for (int i = 0; i < n; i++) { while (!stk.isEmpty() && arr[stk.peek()] >= arr[i]) { stk.pop(); } pse[i] = (stk.isEmpty()) ? -1 : stk.peek(); stk.push(i); } return pse; } /* int bruteFroce(int[]arr){ //this is the brute froce approach //where i generate all subarrays and find mini and sum it up int n = arr.length; int sum = 0; int mod = (int)(1e9 + 7); for(int i = 0;i

[@rushidesai2836]

This was not an easy problem but u taught pretty well.

[@jeet-smokey]

Super explanation. Kudos to your efforts.

[@yoddha621]

Samaj na aya..par sun kar acha laga

[@darkwarrior6767]

If you are getting 73/88 ,use long long for each calculation and take mod in each step of calculation

[@anindyapaul2239]

Boss u r a life saver

[@24_Harsh]

Bawal Guru Kya samjhaye hoo ekdum chamka gya !!

[@nikhilbasir]

Bihari

[@himage6540]

@@nikhilbasir no, maybe from UP. Bihari people dont talk like that

[@radheshyama448]

Superman explanation

[@VardhanMittal]

Great explanation 😊thank you.

[@sudhanvasamaga2360]

This question had come in apple on campus test, If I cleared it back then I would even get the interview call.

[@rushidesai2836]

Apple visited your campus?

[@sudhanvasamaga2360]

@@rushidesai2836 yep for software development ,they took 25 people

[@ToonDubberDuo]

they clearly werent in a great hiring mood if they decided to choose this as the test problem lol

[@prajjwaltripathi2374]

@@ToonDubberDuo Dude they were in great hiring mood if they decided to hire someone and even visited campus. You don't see a apple SWE opening easily, let alone visiting CAMPUS!!

[@ToonDubberDuo]

@@prajjwaltripathi2374 they would barely select 1 or 2 even if they visit.

[@karthik-varma-1579]

17:50 is Quite Intresting edge case.

[@SibiRanganathL]

Understood 😻

[@swarupdas4114]

Optimal 5:30

[@mdashamimad7728]

Pdh hi rha tha playlis se k new video aagya so ya First comment😂😂😂

[@navinvenkat3404]

I lost my life in edge case

[@JunaidShareef-j4u]

You should have to invest ur time to understand this problem like minimum 1hr..

[@DeadPoolx1712]

UNDERSTOOD;

[@pranavmisra5870]

are bhai kuch smjh he nahi aaya

[@pratik4390]

A dryrun with an example would make more sense rather than code

[@ashishkumarmohapatra4671]

didint he did that with the second aaray??

[@arya1129-j7h]

Why S.C = O(5N) and not O(4N)?

[@JAYAKUMARB-t2d]

Edge case 🔥

[@subee128]

Thanks

[@sanchitdeepsingh9663]

thanks sir

[@tarunkr4698]

Thankuuuuuu

[@aryankumar3018]

Understood

[@pullurupraveen9315]

i have doubt suppose if we have have the same two numbers in same sub array range like 8,15,9,13,9,16,17,7 then according to formula the index point from 1 to 6 it counts only 10 but there are 16 its just breaking into parts and missing the two combine parts however in that part also the min is 9 i am thinking 🤔 9 9 13 9 13 9 9 13 9 16 9 13 9 16 17 15 9 13 9 16 17 15 9 13 9 16 15 9 13 9 15 9 13 15 9 13 9 16 17 13 9 16 13 9 9 9 16 17 9 16 according to formula it takes only 10 like before first first 9 there are two elements including that 2*2+after that again 3*2=10 but total there are 16;

[@KartikeyTT]

tysm sir

[@apmotivationakashparmar722]

video for next smaller element has not been uploaded in Stack and Queue Section . Please upload video for that.

[@omkarshendge5438]

i did not understand the concept of previous smaller or equal element

[@shashankvashishtha4454]

understood

[@worldfacts6760]

Not undertood

[@oyeesharme]

tough one 🙃

[@oyeesharme]

but understood

[@oyeesharme]

thanks bhaiya

[@gamingmusic154]

13:21 here the code teels i - pse[i] i have doubt that if present we are at index 5 and pse[i] is 2 so the ans should be 4 elements : 2,3,4,5 but 5-2 is 3 ? plz anyone clarify it

[@manishrohila4033]

class Solution { public: vector findNse(vector& arr, int n) { vector ans(n); stack st; for (int i = n - 1; i >= 0; i--) { while (!st.empty() && arr[st.top()] > arr[i]) { st.pop(); } if (st.empty()) { ans[i] = n; } else { ans[i] = st.top(); } st.push(i); } return ans; } vector findPse(vector& arr, int n) { vector ans(n); stack st; for (int i = 0; i < n; i++) { while (!st.empty() && arr[st.top()] >= arr[i]) { st.pop(); } if (st.empty()) { ans[i] = -1; } else { ans[i] = st.top(); } st.push(i); } return ans; } int sumSubarrayMins(vector& arr) { int n = arr.size(); vector nse = findNse(arr, n); // Corrected initialization vector pse = findPse(arr, n); // Corrected initialization int total = 0; int mod = (int)(1e9 + 7); int left, right; for (int i = 0; i < n; i++) { left = (i - pse[i]); right = nse[i] - i; total = (total + (left * right * 1LL * arr[i]) % mod) % mod; } return total; } };

[@akritipandey1387]

//{ Driver Code Starts #include using namespace std; // } Driver Code Ends class Solution { public: vector lse(vector& arr,int n) { stackst; vector lsee(n); for(int i=0;iarr[i]) st.pop(); //= not boz edge case lsee[i]=st.empty()?-1:arr[st.top()]; st.push(i); } return lsee; } vector rse(vector& arr,int n) { stackst; vectorrsee(n); for(int i=n-1;i>=0;i--) { while(!st.empty() && arr[st.top()]>=arr[i]) st.pop(); rsee[i]=st.empty()?n:st.top(); st.push(i); } return rsee; } int sumSubarrayMins(int N, vector &arr) { long long ans=0; int mod=1e9+7; vectorlsee=lse(arr,N); vectorrsee=rse(arr,N); for(int i=0;i> t; while (t--) { int N; cin >> N; vector arr(N); for (int i = 0; i < N; i++) cin >> arr[i]; Solution obj; cout

[@bhashitmaheshwari5205]

vector pse(vector &A) { int n=A.size(); vectorans(n); stackst; for(int i=0;i=A[i]){ st.pop(); } ans[i]=st.empty() ? -1 : st.top(); st.push(i); } return ans; } vector nse(vector &A){ int n=A.size(); stackst; vectorans(A.size()); for(int i=n-1;i>=0;i--){ while(!st.empty() && A[st.top()]>A[i]){ st.pop(); } ans[i]=st.empty() ? n : st.top(); st.push(i); } return ans; } int sumSubarrayMins(vector& arr) { long long mod=1e9+7; int n=arr.size(); long long total=0; vectorprev=pse(arr); vectornext=nse(arr); for(int i=0;i

[@anindyapaul2239]

these kind of questions are giving me panic attacks, that i should change my focus to service based company only and learn docker and kubernetis.... bcz right now working wd a service based and in microservice architecture. anyone has any views on this ?

[@anurag11-b66]

[@shyamkumar-dev]

Go back to high school and watch it 😆. 9:13

[@pruthvinarayana9568]

🤣🤣🤣

[@suyashtiwari8763]

🔥🔥🔥🔥

[@riyajadhav2905]

Cam anyone rell me why is je using mod

[@sujalthakkar2118]

but i first calculated NSE then cleared the stack, then calculated PSE as well as the sum in the same iteration as i want the NSE and PSE of the same index so it seemed feasible to do. And it got excepted just had to mod it with 1e9+7 . t.c.- O(3n), s.c.-O(3n) what's problem if i don't consider the edgecases?

[@saqibaqeel9196]

Can some one explain why index based??

[@yashwanthsai7808]

waiting for tuf+

[@krs7936]

what's that?

[@agrawalmitesh4395]

maja avi gai

[@pranavh8583]

i think i cant solve it in test.

[@NetajiSaiSuru]

Anyone facing the problem in passing last test case 88th one.

[@saikishorebagula6571]

total = (total + (left * right * 1LL * arr[i]) % mod) % mod; Use this 1LL

[@SanchitNarang-w8h]

can anyone help me in the edge case?

[@sukhii0220]

9:06 if someone please explain this how 12 subarray is generated what maths behind it please someone explain it

[@kushalsinha6917]

this is someone's else comment but I'm leaving it here For every subarray of left(i.e 4 subarrays) we have 3 options to combine from right so -->for first subarray there will be 3 options -->for second subarray 3 options -->for third subarray 3 options --> for forth subarray 3 options So total will be 4 * 3 =12 Or 3 + 3 + 3 +3 = 12 Now understand with the example in video We have 4 subarrays on right and 3 on left Now we can take 4 6 7 with either 3 or with 3 7 or with 3 7 8 (this will create 3 subarrays with lowest value 3) Then we can take 6 7 with 3 or with 3 7 or with 3 7 8 (this will create 3 subarrays with lowest value 3) And same for 7 and 3 Thus total will be 3 + 3 + 3 +3 = 12 or we can say 4* 3 = 12

[@SiddhiLandage]

Can u please give the example actually I don't get it much

[@KartikeyTT]

7:35

[@MayankSengar-y3g]

class Solution { public :int mod = 1000000007; public: int findpse(vector& arr,int id){ stacks; vectorv(arr.size(),-1); for(int i=0;iarr[i]){ s.pop(); } if(s.empty()){ s.push(i); } else{ v[i]=s.top(); s.push(i); } } return v[id]; } int findnse(vector& arr,int id){ stacks; vectorv(arr.size(),arr.size()); for(int i=arr.size()-1;i>=0;i--){ while(!s.empty() &&arr[s.top()]>=arr[i]){ s.pop(); } if(s.empty()){ s.push(i); } else{ v[i]=s.top(); s.push(i); } } return v[id]; } int sumSubarrayMins(vector& arr) { // vectorv; // int sum=0; // int n=arr.size(); // int mini; // for(int i=0;i

[@__kasim__khan__]

I was able to solve this problem in one pass and using O(2N) space. class Solution { public: #define mod 1000000007 int sumSubarrayMins(vector& arr) { int n = arr.size(); stack st; long long ans = 0 ; vector dp(n , 0); for(int i = n-1 ; i >= 0 ; i--) { int curr = arr[i]; long long currSum = 0; while(!st.empty() && curr

[@devjindal8309]

Can anyone explain how those subarrays count =4*3=12?

[@vivek.chandravanshi]

there are 4 larger elements on the left(including i) and 3 larger elements on the right. starting from EACH of the 4 left elements, we have 3 end points on the right, so number of subarrays having i as smallest element = 4*3

[@b_technical4017]

@@vivek.chandravanshi Bro can you explain in more detail please? I did not understand

[@DrawwithNavi]

@@b_technical4017 To determine how many contiguous subarrays in the given array [ 4 , 6 , 7 , 3 , 7 , 8 ] [4,6,7,3,7,8] contain the element 3, we can follow these steps: Identify the position(s) of the element 3 in the array. Calculate the number of contiguous subarrays that include this position. Let's break it down step by step: Identify the position of the element 3: The element 3 is at index 3 (considering 0-based indexing). Calculate the number of subarrays containing the element 3: The element 3 is at index 3. To form a subarray containing the element at index 3, we can start the subarray from any index ranging from 0 to 3 (inclusive) and end it at any index ranging from 3 to 5 (inclusive). The number of ways to choose a starting index (from 0 to 3) is 4, and the number of ways to choose an ending index (from 3 to 5) is 3. Thus, the total number of subarrays containing the element 3 is calculated as follows: Number of subarrays = 4 × 3 = 12 Number of subarrays=4×3=12 So, there are 12 contiguous subarrays that will have the element 3.

[@sanchitdeepsingh9663]

@@vivek.chandravanshi thanks

[@randomrandom-n5s]

@b_technical4017 supposing you have 4 elements on left, and 3 on right ( including current in both ), now total possible combinations of subarrays will be 4*3. How? say the 4 elements are like(naming it row-1) : __ __ __ __ and three elements are like(naming it row-2) : __ __ __ try making line from every row 1 " __ " to every row 2 " __ " . total number of lines will be 12. how this is related to sub arrays ? now think of those " __ " as the first index for that in row 1 and think of those " __ " as the last index for that in row 2 since we got first and last index, every subarray can be seen.

[@rahulsidhu5945]

Hey Striver I write the same code that you written in your video. But it is giving me TLE for very big inputs. Please check where I am doing wrong """class Solution { public: vector findNse(vector & arr,vector & nse){ int n=arr.size(); int i=n-1; stacks1; while(i>=0){ if(s1.empty()){ //for holding the "-" property nse[i]=n; s1.push(i); i--; } else if(arr[s1.top()]arr[i]){ st.pop(); } } } return pse; } int sumSubarrayMins(vector& arr) { int n=arr.size(); vectornse(n); vectorpse(n); int total=0; int mod=1e9+7; for(int i=0;i

[@anilsonawane1925]

Bro declare the mod globally for ex:) class Solution { public int mod = 1000000007; public int[] prevSmallerEqualElementIndex(int[] arr, int n) { int[] ans = new int[n]; Stack st = new Stack(); for (int i = 0; i < n; i++) { while (!st.isEmpty() && arr[st.peek()] > arr[i]) { st.pop(); } ans[i] = st.isEmpty() ? -1 : st.peek(); st.push(i); } return ans; } public int[] nextSmallerElementIndex(int[] arr, int n) { int[] ans = new int[n]; Stack st = new Stack(); for (int i = n - 1; i >= 0; i--) { while (!st.isEmpty() && arr[st.peek()] >= arr[i]) { st.pop(); } ans[i] = st.isEmpty() ? n : st.peek(); st.push(i); } return ans; } public int sumSubarrayMins(int[] arr) { int n = arr.length; int[] prev = new int[n]; int[] next = new int[n]; prev = prevSmallerEqualElementIndex(arr, n); next = nextSmallerElementIndex(arr, n); long sum = 0; for (int i = 0; i < arr.length; i++) { long left = i - prev[i]; long right = next[i] - i; sum = (sum + (left * right * arr[i]) % mod) % mod; } return (int) sum; } }

[@AyushVerma-wu3nn]

The mistake seems to be while calculating the PSE and NSE , you are doing inside of a for loop for each element, you can do that before starting the iteration of the Array loop.

[@MayankSengar-y3g]

same bro

[@harikareddy-o4f]

First comment bhaiya

[@rajvardhansinghthakur6481]

First To comment, Thanks bro for the great content 👏

[@NoBakwas]

Why is the space complexity O(5n) and not O(4n) ?

[@misterbean6674]

same ques. it should be 4N imo.

[@sukhii0220]

brother for loop for summing ke liye run kra h uska O(N) bhi toh plus krega na phele ke O(2n) + o(2n) mai

[@misterbean6674]

@@sukhii0220 To fir TC hi 5N hoga na, space to 4N rhega na.

[@sushmi6400]

Why left=i - pse[i]..? We have get the pse[i] index no..?

[@agneshk1012]

instead of pushing arr[i] to stack, he is pushing just i, so pse[i] contains index of previous smaller element of arr[i]

[@sushmi6400]

@@agneshk1012 hey thanks man...!

[@soumyadey4500]

why in the PSE function "nums[st.top()] > nums[i]" is taken instead of "nums[st.top()] >= nums[i]"

[@emperorgaming3704]

bro why are we taking nums[st.top()] and not st.top() only??

[@aaravgulati2]

@@emperorgaming3704 Because you need to compare the value not the index, it is previous smaller element not previous smaller index

[@emperorgaming3704]

@@aaravgulati2 oo yes bro Thanks

[@rutujashelke4208]

Understood

[@Shivi32590]

understood