Leetcode 907 Sum of Subarray Minimums | Hindi | Explanation + Code

#anuragcodes #leetcodehindi

[vaishnaviupadhyay]

First corrected solution

class Solution {
public static int sumSubarrayMins(int N, int[] arr) {
int sum = 0;
for(int i=0;i<N;i++){
int min = arr[i];
for(int k=i;k<N;k++){
if(min > arr[k]){
min = arr[k];
}

sum += min;
}
}
return sum;
}
}

[Saitama-kfoy]

hindi mai details miss nhi hoti hai, thanks brother.

[tanusingh]

There is a connection in the naive approach, instead of arr[i] inside the second for loopp, it will be arr[k]

[DEEPAK-tdqw]

thanku so much for best explanation of this question
For c++ users, can go with this. use only indexes for pushing in stack as we did in next smaller element.

class Solution {

public: int MOD = 1e9 + 7;
public:
int sumSubarrayMins(vector<int>& A) {

int n = A.size();

vector<int> left(n), right(n);

stack<int>st;

//Left
st.push(0);
left[0] = 1;
for(int i=1; i<n; i++)
{
while(!st.empty() && A[i] < A[st.top()])
st.pop();

if(st.empty())
left[i] = i+1;
else
left[i] = i - st.top();

st.push(i);

}

while(st.size())
st.pop();

// Right
st.push(n-1);
right[n-1] = 1;
for(int i=n-2; i>=0; i--)
{
while(!st.empty() && A[i] <= A[st.top()])
st.pop();

if(st.empty())
right[i] = n-i;
else
right[i] = st.top()-i;

st.push(i);
}



int res = 0;
for(int i=0; i<n; i++)
{
long long prod = (left[i]*right[i])%MOD;
prod = (prod*A[i])%MOD;
res = (res + prod)%MOD;
}

return res%MOD;
}


};

[abhiroopsingh]

Best explaination available on youtube.🔥

[avinashjaiswal]

Thanks, Currently one test case is failing we can use long array for leftmin and rightMin. for sum we can use long data type. after this it is pass all test cases

[avegeta]

The only clear explanation for this problem on youtube!

[mayanksrivastava]

Amazing explanation.. after browsing thru so many videos, i finally understood the core explanation.. thanks a ton.. please keep making tutorials

[MadaraUchiha-cq]

greater explanation, bhaiya.
was trying to solve this question for more than a day.
thanx

[tejuschaturvedi]

Thank you for the detailed explanation . 👏

[sharuk]

awesoemeee explanationnn.mzaa a gya bhai, Here is some Change after some Test case updated by later
long res = 0, mod = (int)Math.pow(10, 9)+7;
for (int i = 0; i < n; i++)
res = (res + (long)arr[i] * left[i] * right[i] ) % mod;
return (int)res;
make this it will easily submitted

[siddhantgupta]

const int mod=1e9+7;
int sumSubarrayMins(int n, vector<int> &arr) {

vector<int> sum(n);
stack<int> s;

int j, res = 0;

for (int i = 0; i < n; ++i) {

while (!s.empty() && arr[s.top()] > arr[i]) {
s.pop();
}

j = !s.empty() ? s.top() : -1;
sum[i] = ((j >= 0 ? sum[j] : 0) + (i - j) * arr[i]) % mod;
s.push(i);
}

for(auto x : sum)
res=(res+x)%mod;

return res;
}

[navadeepbitra]

Python one's
sum_list = []
elements = [1, 2, 3]
for x in range(0, len(elements)):
sublist = elements[x:]
for y in range(len(sublist)):
super_sub_list = sublist[0:y + 1]


print(sum(sum_list))

[chabhishyam]

Solution:

class Solution {
int mod=(int)Math.pow(10, 9)+7;
public class Pair{
int e;
int c;
public Pair(int e, int c){
this.e = e;
this.c = c;
}
}
public int sumSubarrayMins(int[] arr) {

int n =arr.length;
int[] left = getLeftMin(arr, n);
int[] right = getRightMin(arr, n);
long sum=0;
for(int i=0; i<arr.length; i++){
sum = (sum+
}
return (int)sum;

}


public int[] getLeftMin(int[] arr, int n) {
int[] a = new int[n];
Stack<Pair> s = new Stack<>();
for(int i = 0; i< n; i++){
int count = 1;
while(!s.isEmpty() && s.peek().e > arr[i]){
count+=s.peek().c;
s.pop();
}
s.push(new Pair(arr[i], count));
a[i] = count;
}
return a;
}

public int[] getRightMin(int[] arr, int n) {
int[] a = new int[n];
Stack<Pair> s = new Stack<>();
for(int i = n-1; i>=0; i--){
int count = 1;
while(!s.isEmpty() && s.peek().e >= arr[i]){
count+=s.peek().c;
s.pop();
}
s.push(new Pair(arr[i], count));
a[i] = count;
}
return a;
}
}

[ananysharma]

Thank you so much, Best Explanation of this Question and other applications of Monotone Stack.❤️❤️

[ImPushpendraPal]

Best part unlike other gandu youtuber you directly jump on the problem and explained everything in detail. Thanks, nice video.

[gagandeep-sbjm]

bro there is one mistake change arr[i] to arr[k] you mistakenly write arr[i] instead of arr[k] in if(min>arr[i) condition

[satyaganesh]

great explanation broo.. Please keep doing more...
the way u said brute force first and optimized second is way too good.

[studyWithReet]

Fantastic and commendable explanation !!!!