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.
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.
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
#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
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;
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 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.
@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.
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 ?
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
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; } }
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.
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
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(); }
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
![Good Book about Low-Level C++ [from a quant dev]](/img/1.gif)
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.
Tutor matters :)
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.
Thanks bro
How did it arrive to the multiplication part directly in video ?
went complete blank after 20th minute man! very diffcult to understan this stack method
watch the previous videos of next smaller / previous smaller, he has explained in detail
Edge case handling: Make either one of PSE/NSE strictly smaller and other one smaller or equal to
Man, thnxs a lot. I was waiting eagerly for your Stack & Queues playlist. Thnxs a lot man.
I think I have not studied high school properly 🥲🥲🥲
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
Thank you for such a great explaination . Edge Case needs to be remembered in this question.
17:50 is Quite Intresting edge case.
The better approach is actually very hard to understand but after watching the video 3 times i understood it.
Thanks Striver Bhaiya ❣️
When they don't want to hire you this question comes up in the interview
Super explanation. Kudos to your efforts.
4:56 Why tf is interviewer always unhappy
Then ask him to solve it by his own. XD
@@rajibdas5574 real
Superman explanation
got it after watching it 3 times........
If you are getting 73/88 ,use long long for each calculation and take mod in each step of calculation
Boss u r a life saver
Bawal Guru Kya samjhaye hoo ekdum chamka gya !!
Bihari
@@nikhilbasir no, maybe from UP. Bihari people dont talk like that
This was not an easy problem but u taught pretty well.
#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
This question had come in apple on campus test, If I cleared it back then I would even get the interview call.
Apple visited your campus?
@@rushidesai2836 yep for software development ,they took 25 people
they clearly werent in a great hiring mood if they decided to choose this as the test problem lol
the edge case will be the death of me
Great explanation 😊thank you.
Samaj na aya..par sun kar acha laga
are bhai kuch smjh he nahi aaya
Understood 😻
Thankuuuuuu
tysm sir
video for next smaller element has not been uploaded in Stack and Queue Section . Please upload video for that.
UNDERSTOOD;
Thanks
thanks sir
Understood
You should have to invest ur time to understand this problem like minimum 1hr..
Edge case 🔥
understood
I lost my life in edge case
Pdh hi rha tha playlis se k new video aagya so ya First comment😂😂😂
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;
i did not understand the concept of previous smaller or equal element
Can anyone explain how those subarrays count =4*3=12?
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
@@vivek.chandravanshi Bro can you explain in more detail please? I did not understand
@@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.
@@vivek.chandravanshi thanks
@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.
Not undertood
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 ?
tough one 🙃
but understood
thanks bhaiya
Go back to high school and watch it 😆. 9:13
🤣🤣🤣
🔥🔥🔥🔥
Can some one explain why index based??
Why is the space complexity O(5n) and not O(4n) ?
same ques. it should be 4N imo.
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
@@sukhii0220 To fir TC hi 5N hoga na, space to 4N rhega na.
i think i cant solve it in test.
Anyone facing the problem in passing last test case 88th one.
total = (total + (left * right * 1LL * arr[i]) % mod) % mod;
Use this 1LL
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;
}
};
waiting for tuf+
what's that?
maja avi gai
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
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;
}
}
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.
same bro
9:06 if someone please explain this how 12 subarray is generated what maths behind it please someone explain it
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
Can u please give the example actually I don't get it much
can anyone help me in the edge case?
7:35
First To comment, Thanks bro for the great content 👏
//{ 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
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
First comment bhaiya
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
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
Why left=i - pse[i]..?
We have get the pse[i] index no..?
instead of pushing arr[i] to stack, he is pushing just i, so pse[i] contains index of previous smaller element of arr[i]
@@agneshk1012 hey thanks man...!
why in the PSE function "nums[st.top()] > nums[i]" is taken instead of "nums[st.top()] >= nums[i]"
bro why are we taking nums[st.top()] and not st.top() only??
@@emperorgaming3704 Because you need to compare the value not the index, it is previous smaller element not previous smaller index
@@aaravgulati2 oo yes bro
Thanks
Understood
understood