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.
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😍👏👏.
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.
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.
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
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]
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
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
Finally after watching the solution in 4 different channels I understood it here
This is the greatest explanation among all the explanations available in yt
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
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 😅.
24:06 this was brilliant !
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.
loved your way of explanation❤
thank you this is the best explanation I found :)
thankyou so much buddy! very nice
totally understood ! thank you so much bro
amazing explanation bro
Excellent!
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.
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
How aryan can maintain work n leetcode parallely
finally a good explaination.
Given constraint is 3x10^4 , then O(n^2) should work then why it's TLE showing
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)
Brilliant explanation♥
Bhai aapne cnt ko tho badhaya hi nahi jab voh while loop main nahi ghus raha hai tab???
#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
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
watched
thanksssss
did it by myself in half hour
Showing TLE
Fucked up my mind!
🧡❤❤❤❤❤❤❤❤❤
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
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
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