Sum of Subarray Minimums | Leetcode | Medium | Java | Striver's A to Z DSA Course/Sheet

Certainly! In this problem-solving scenario, a fundamental understanding of stack operations is crucial, specifically pertaining to two key concepts: identifying the previous smaller element and the next smaller element within an array. The approach for finding the previous smaller element is explained in this video itself.
The essence of the question lies in grasping the intuitive notion of determining a range where a specific element is the smallest. This range subsequently serves as the basis for identifying all subarrays in which the given element functions as the minimum value.

Other problems for practice:

[saurabhchaudhari]

class Solution {
private:
vector<int>
int n=arr.size();
vector<int>ans(n);
stack<int>st;

for(int i=0;i<n;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();
}

st.push(i);
}

//push
return ans;
}

vector<int>
int n=arr.size();
vector<int>ans(n);
stack<int>st;

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<int>& arr) {
int n=arr.size();
int MOD =





long long sum=0;
for(int i=0;i<n;i++){
if(next[i]==-1){
next[i]=n;
}

//to find total subarrays in which arr[i] is minimum
int rightlen=next[i]-i;
int leftlen=i-prev[i];

long long

sum=(sum+product)%MOD;
}
return sum;
}
};

[GOAT_Nation]

Nice explanation ! Sometimes it is good to explain just what is needed.. Some people are explaining too much which confuses many of us.

[aryansinha]

why are we doing i-prev[i] for first and next[i]-i for second

[shashankvashishtha]

try to keep already taught things as a black box, like striver do "go back and watch that video" it will improve the quality of content, best of luck.

[manirathore]

nice ! but you should have done the dry run in the end

[aryansinha]

Next greater to right, why are we putting arr size in the ans array

[vaibhavdixit]

hey pls tell why u wrote i - prevsm[i] and nextsm[i] - i ?

[paragsharma]

you should be louder, because everyone's speaker is not good.(baki sab teek hai👍) Jai shri krishna 🙏

[ramkrushnaparkipandla]

Your ans is good [O(n) ]but you beats only 10%

[astronautgamer]

plz explain the topic more clearly, half of the video is typing code, instead of that explain the code how it working.

[dayashankarlakhotia]

public int sumSubarrayMins (int[]arr){
int
int[]st=new int[arr.length+1];
int idxSt=0;long ans=0;
for(int i=1;i<=arr.length;i++){

int idx=st[idx--];
int leftIdx =idxSt<0?-1:st[idxSt];

}
st[++idxSt]=i;
}
return (int)(ans%mod);
}