907. Sum of Subarray Minimums | Monotonic Stack | Brute - Better - Optimal
Vložit
- čas přidán 27. 07. 2024
- In this video, I'll talk about how to solve Leetcode 907. Sum of Subarray Minimums | Monotonic Stack
Problem Link: leetcode.com/problems/sum-of-...
Checkout DSA-169 Series: • Aryan DSA-169 Series |...
100Days 100k Placements: • 100 Days 100K Placement
Let's Connect:
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / ez.pz.dsa
📱Telegram : t.me/aryan_mittal_group
🤖 Github: github.com/aryan-0077
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Timelines✨
0:00 - Problem Explanation
0:57 - Brute Force
1:55 - Better
3:52 - Optimal - Using Monotonic Stack
17:36 - Dry Run
27:10 - Code Explanation
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms
Don't know what LC smoked, before placing this Problem as Medium 🫠🫠
Weed 😢
This question ate my brain for the past two hours, I've tried all other videos available for this question, including big names like neetcode, but your solution is the only one that I could understand from start to finish. Well done sir. Earned a subscribe.
Same here
This is the greatest explanation among all the explanations available in yt
Finally after watching the solution in 4 different channels I understood it here
bro, what an amazing explanation.
now I don't have any doubt left after watching this video.
and now I can easily solve the problems of same pattern.
Thank you very much for such a great explanation😍👏👏.
Thank you so much for explaining HOW the count works. I was trying to recall what I learned in my combinatorics class years ago lol
finally a good explaination.
thankyou so much buddy! very nice
loved your way of explanation❤
totally understood ! thank you so much bro
Excellent!
I was pissed I couldn't solve this problem but, now I feel a little better considering how hard this was. Also please make a video on KMP 😮💨, waiting from the previous weekly contest.
That video is out bro, that day only it came - Write on yt - Kmp by Aryan Mittal, you will get the video ❤️❤️🫂
@@ARYANMITTAL damn i completely missed it 😅.
thank you this is the best explanation I found :)
Great solution. I like how you worked out the problem step by step completely before going to the code. You made a hard problem seem easy.
How aryan can maintain work n leetcode parallely
24:06 this was brilliant !
Brilliant explanation♥
I cant get a hold on why left*right works i get that it tells us that how many subarrays will include that particular number, but cant understand why it works?? anyone explain if possible, Great video by the way....Clear and precise.
Actually I'm not good at hard problems but after reading the problem I don't know how it clicked my mind and cracked the monotonic stack solution.
Bro can u solve Sum of Subarray Ranges as well.
Thanks in advance !
superb explanation, really like it (tired of python explanation :D)
thanksssss
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
Bhai aapne cnt ko tho badhaya hi nahi jab voh while loop main nahi ghus raha hai tab???
Given constraint is 3x10^4 , then O(n^2) should work then why it's TLE showing
Showing TLE
Fucked up my mind!
#include
#include
#include
using namespace std;
class Solution {
public:
int sumSubarrayMins(vector& arr) {
stack st;
vector next_lesser(arr.size(), arr.size());
vector prev_lesser(arr.size(), -1);
for (int i = 0; i < arr.size(); i++) {
while (!st.empty() && arr[st.top()] >= arr[i]) {
next_lesser[st.top()] = i;
st.pop();
}
prev_lesser[i] = st.empty() ? -1 : st.top();
st.push(i);
}
long long answer = 0;
double mod = 1e9 + 7;
for (int i = 0; i < arr.size(); i++) {
long long left = i - prev_lesser[i];
long long right = next_lesser[i] - i;
answer += arr[i] * left * right;
answer %= (long long)mod;
}
return (int)answer;
}
};
int main() {
Solution sol;
vector arr = {3, 1, 2, 4};
cout
stack st;
st.push(-1);
int n=arr.size();
vector dp(n);
long long ans=0;
for(int i=0;iarr[i-1])
dp[i]=(arr[i]+dp[i-1]);
else
{
// 2nd case
while(st.top()!=-1 and arr[i]
bro can you explain it please
bhaiya to improve logical thinking should i need to do cp bhaiya i am in third year i am not getting interest any tips bhaiya
Correct me if I'm wrong, but I believe the code fails for brute and better. Because it is not taking into account single element subarrays. Thank you for the stack solution tho, I was stuck on it the whole day lol
did it by myself in half hour
Why Wrong Answer
Runtime: 7 ms
Case 1
Case 2
Input
arr =
[11,81,94,43,3]
Output
384
Expected
444
class Solution {
public:
int sumSubarrayMins(vector& arr) {
int MOD = 1e9 + 7;
int n = arr.size();
vector left(n,0), right(n,0);
stacksLeft, sRight;
for(int i=0;iarr[i]){
cnt+=sLeft.top().second;
sLeft.pop();
}
sLeft.push({arr[i],cnt});
left[i]=cnt;
}
for(int i=n-1;i>=0;i--){
int cnt=1;
if(!sRight.empty() && sRight.top().first>=arr[i]){
cnt+=sRight.top().second;
sRight.pop();
}
sRight.push({arr[i],cnt});
right[i]=cnt;
}
long long sum = 0;
for(int i=0;i