L10. Sum of subarray ranges | Stack and Queue Playlist

[@anshusorrot316]

completed this problem myself before watching the video thanks to previous video

[@vinayjoshi8714]

Was able to do it on my own thanks to the previous video

[@CodeRocks-z6g]

This question came in my recent interview I did the brute force and getting tle I wish I had watched this earlier

[@Anoint2612]

bro can you please tell for which company this Qs came? also was it on or off?

[@apmotivationakashparmar722]

Hey Striver , Articles of many video solutions are missing as well as many video Solutions have not been uploaded such as in complete String
and some part in recurrsion . Can you please upload ? 😀😀

[@huungryyyy]

Love ur Contact😍😍😍😍

[@PavanKumar-rb9iw]

Contact?

[@KeshabDas-c5c]

​@@PavanKumar-rb9iw😂😂

[@clustercate]

class Solution {
public:
vector findNSE(vector& nums) {
int n = nums.size();
vector nse(n);
stack st;
for(int i=n-1; i>=0; i--) {
while(!st.empty() && nums[st.top()] >= nums[i])
st.pop();
nse[i] = st.empty() ? n : st.top();
st.push(i);
}
return nse;
}
vector findPSEE(vector& nums) {
int n = nums.size();
vector psee(n);
stack st;
for(int i=0; i nums[i])
st.pop();
psee[i] = st.empty() ? -1 : st.top();
st.push(i);
}
return psee;
}
long long sumSubarrayMins(vector& nums) {
vector nse = findNSE(nums);
vector psee = findPSEE(nums);
long long total = 0;
for(int i=0; i=0; i--) {
while (!st.empty() && nums[st.top()] < nums[i])
st.pop();
ngee[i] = st.empty() ? n : st.top();
st.push(i);
}
return ngee;
}
vector findPGE(vector& nums) {
int n = nums.size();
vector pge(n);
stack st;
for (int i=0; i

[@clustercate]

@vivekkallani690 correct one

[@HimanshuSharma-ow9ft]

Can u explain what is this 1LL?

[@clustercate]

@@HimanshuSharma-ow9ft long long

[@shivapranav3185]

thankyou for the wonderful explanation!!!!!!

[@apmotivationakashparmar722]

Thank you so much for this video 🙏🙏.

[@trashcan-md7cw]

long long subArrayRanges(vector& nums) {
int n = nums.size();
vector pse(n), nse(n), pge(n), nge(n);
stack st;

//find previous smaller or equal elements
for(int i = 0; i < n; i++){
while(!st.empty() && nums[st.top()] >= nums[i]){
st.pop();
}
if(st.empty()) pse[i] = -1;
else pse[i] = st.top();
st.push(i);
}
//clear the stack
while(!st.empty()) st.pop();
//find previous greater or equal elements
for(int i = 0; i < n; i++){
while(!st.empty() && nums[st.top()] = 0; i--){
while(!st.empty() && nums[st.top()] > nums[i]){
st.pop();
}
if(st.empty()) nse[i] = n;
else nse[i] = st.top();
st.push(i);
}
//clear the stack
while(!st.empty()) st.pop();
//find next greater elements
for(int i = n-1; i >= 0; i--){
while(!st.empty() && nums[st.top()] < nums[i]){
st.pop();
}
if(st.empty()) nge[i] = n;
else nge[i] = st.top();
st.push(i);
}
long long res = 0;
for(int i = 0; i < n; i++){
res = res + (long long)(nums[i]*(long long)((i - pge[i]) *(nge[i] - i))) - (long long)(nums[i]*(long long)((nse[i] - i) * (i - pse[i])));
}
return res;
}

[@sujalthakkar2118]

understood maan!

[@oyeesharme]

thanks bhaiya

[@MaheshPatil-of1zy]

Use The Logic Of Next Greater Element done and dusted

[@twinklelight9829]

could you please provide the code for your approach, that would be very helpful

[@prathmeshparab7046]

Amazing ..
👍

[@DeadPoolx1712]

UNDERSTOOD;

[@Luna-vk9xy]

can someone tell me what's wrong with this code? it returns wrong answer for a big TC
class Solution {
public:
vector nextSmallerElement(vector& arr){
vector res;
stack s;
int n = arr.size();
for(int i=n-1; i>=0; i--){
while(!s.empty() && arr[s.top()] >= arr[i])
s.pop();
res.push_back(s.empty()? n : s.top());
s.push(i);
}
reverse(res.begin(), res.end());
return res;
}
vector prevSmallerOrEqualElement(vector& arr){
vector res;
stack s;
int n = arr.size();
for(int i=0; i arr[i])
s.pop();
res.push_back(s.empty()? -1: s.top());
s.push(i);
}
return res;
}
vector nextGreaterElement(vector& arr){
vector res;
stack s;
int n = arr.size();
for(int i=n-1; i>=0; i--){
while(!s.empty() && arr[s.top()]

[@AmirDhahri-rn3cg]

Awesome ♥️🥰🥰

[@aryankumar3018]

Understood

[@KartikeyTT]

tysm sir

[@rahulmandal4007]

Thank you bro

[@MJBZG]

understood

[@aryasharma69]

Are you going to upload videos for recursion playlist???????????????????????????????????????????????

[@abudanish196]

He already did long back. Go check his channel.

[@aryasharma69]

@@abudanish196 i guess you need to check again, half of them are empty

[@vivekkallani690]

class Solution {
public:
vector psee(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();
}
ans[i] = st.empty() ? -1 : st.top();
st.push(i);
}
return ans;
}
vector nse(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();
}
ans[i] = st.empty() ? n : st.top();
st.push(i);
}
return ans;
}
vector pgee(vector& arr, int n) {
vector ans(n);
stack st;
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] = 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 = psee(arr, n);
vector next = nse(arr, n);
long long sum = 0;
long long mod = 1e9 + 7;
for (int i = 0; i < n; i++) {
long long left = i - prev[i];
long long right = next[i] - i;
sum = (sum + (left * right % mod) * arr[i] % mod) % mod;
}
return (int)sum;
}
int sumSubarrayMax(vector& arr) {
int n = arr.size();
vector prev = pgee(arr, n);
vector next = nge(arr, n);
long long sum = 0;
long long mod = 1e9 + 7;
for (int i = 0; i < n; i++) {
long long left = i - prev[i];
long long right = next[i] - i;
sum = (sum + (left * right % mod) * arr[i] % mod) % mod;
}
return (int)sum;
}
long long subArrayRanges(vector& nums) {
long long maxSum = sumSubarrayMax(nums);
long long minSum = sumSubarrayMins(nums);
return maxSum - minSum;
}
};
can anyone please tell me what's wrong in this approach it passed 30 testcases and failed for larger values

[@akshatopam6171]

don't use mod the question doesn't demand mod. It alters the solution.

[@sunkarasudharshan2493]

in subarraymax and subarraymin give return type as long.Instead of int.

[@shreyxnsh.14]

complete cpp code:
class Solution {
public:
vector findNse(vector &arr) {
vector nse(arr.size());
stack st;
for (int i = arr.size() - 1; i >= 0; --i) {
while (!st.empty() && arr[st.top()] >= arr[i]) {
st.pop();
}
nse[i] = st.empty() ? arr.size() : st.top();
st.push(i);
}
return nse;
}
vector findPsee(vector &arr) {
vector pse(arr.size(), -1);
stack st;
for (int i = 0; i < arr.size(); ++i) {
while (!st.empty() && arr[st.top()] > arr[i]) {
st.pop();
}
pse[i] = st.empty() ? -1 : st.top();
st.push(i);
}
return pse;
}
long long sumSubarrayMins(vector& arr) {
int MOD = (int)1e9 + 7;
long long sum = 0;
vector nse = findNse(arr);
vector pse = findPsee(arr);
for (int i = 0; i < arr.size(); ++i) {
long long left = i - pse[i];
long long right = nse[i] - i;
sum = (sum + (left * right * 1LL * arr[i]));
}
return sum;
}
vector nextGreaterElements(vector& nums) {
int n = nums.size();
vector nge(n, n);
stack st;
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && nums[st.top()] < nums[i]) {
st.pop();
}
if (!st.empty()) {
nge[i] = st.top();
}
st.push(i);
}
return nge;
}
vector previousGreater(vector &nums) {
int n = nums.size();
vector maxPrev(n, -1);
stack st;
for (int i = 0; i < n; i++) {
while (!st.empty() && nums[st.top()]

[@Shivi32590]

understood