Closed the video three times in three days , was not able to understand the approach or you can say was scared of the optimal approach and skipped the whole question many time but didn't gave up Its day 4 and now i have understood everything. I am quite proud of myself ;-).
For next or previous smaller element, in the while loop (which pops out elements), the condition we use is ">=" (greater than or equal to). Here, in the single pass approach we are using ">" (strict greater than). There are implications with duplicate elements in the input (just for fun understanding): Consider the input is [2, 2, 2, 2]: Case 1: If we were to take ">" (strict greater than), the area computed for each index will be 8, 6, 4 and 2 respectively. The last 2 (index 3) will be popped first and it will have the previous 2 (index 2) sitting on top of the stack, giving it an area of 2 x (4 - 2 - 1) = 2. For the next element, it will be 2 x (4 - 1 - 1) = 4, and so on. Case 2: If we were to take ">=" (greater than or equal to), the area computed for be reversed, i.e. 2, 4, 6 and 8 respectively. The first element (index 0) will be popped first when looking at second element (index 1), giving out area = 2 x (1 - (-1) - 1) = 2. Then second element will be popped while looking at the third element, and so on. In either case, the intermediate area computations (with duplicate elements sitting next to each other) are incorrect, because ideally in above case one would expect the area of 8 for each of the element. However, the maximum area will appear with one of the element, so we do get correct answer.
I just closed the video when I understood I have to find prev and next smaller element. But After I submitted I saw my Time and then I came back to discover that there is more to this ques !! I have solve this in one iteration !!
At first this problem appeared to be a lot intimidating but I gave time to the striver's Question description & bingo!! I cracked it to be a PSE & NSE problem, Striver🔥Thanks for building the intuition in prev lectures, guys who are coming to this video directly, plz plz first go to the next greater ele video
instead of another while loop you can also add -1 element to start and end of array and then proceed as same class Solution { public: int largestRectangleArea(vector& h) { h.insert(h.begin(),-1); h.push_back(-1); int n=h.size(); int maxi=-1; stack st; for(int i=0;ih[st.top()])st.push(i); else{ while(!st.empty() && h[st.top()]>h[i]){ int height=h[st.top()]; int pse=0; st.pop(); if(!st.empty())pse=st.top(); maxi=max(maxi,height*max(1,(i-pse-1))); } st.push(i); } } return maxi; } };
after watching the optimal approach multiple times in couple of days i was unable to understand it but on 5th and 6th day i watched it again and got every single bit of it understood everything completely optimal approach dekh kr aur smjh kr maza aagaya sach mai....
class Solution { public: int largestRectangleArea(vector& heights) { stack st; int maxArea = 0; int n = heights.size();
for(int i = 0; i < n; i++) { while(!st.empty() && heights[st.top()] > heights[i]) { int element = st.top(); st.pop(); int nse = i; int pse = st.empty() ? -1 : st.top(); maxArea = max(heights[element] * (nse - pse - 1), maxArea); } st.push(i); }
while(!st.empty()) { int nse = n; int element = st.top(); st.pop(); int pse = st.empty() ? -1 : st.top(); maxArea = max(heights[element] * (nse - pse - 1), maxArea); }
If you are able to understand the approach 2, just watch Neetcode's explanation for the same problem and then come back to striver's explanation. You will understand the problem clearly then.
I have an issue with the optimal approach. What if there is a value that is to be popped and the top value is equal to it? Suppose the given vector is 2 3 2 1, so 2 is pushed at i = 0, then 3 is pushed at i = 1, then 3 is popped and maxarea is calculated for i = 2, there nse is 2 and pse is 0, and 2 is pushed. But then, for i = 3, before 1 is pushed 2 is popped, there is nse is 3, it's fine. But pse is becoming 0 there because s.top() is still 2, but the same height can't be pse because it is added in the width. There is my issue. Instead of pse becoming -1, here pse becomes 0. Can someone plz explain?
You're correct. Let me try to explain. Its little intuitive. For the 3rd element, we indeed get a wrong answer. if you print the Areas at each iteration, you can verify it. Yet the overall answer comes out to be correct, because the case ignored by this 2, is covered by 1st 2. Think about it, when you're at i=0, the max width is 3 (0,1,2 positions), and the same is at i=2; so, even if this area is not covered at i=2, it will be covered by i=0, the original guy that arrived, as for it, the right is same as the right for i=2 i.e nse = 1 at posi 3. but for i=0, pse will be still -1, which may not have been covered by i=2, but this guy covers it. If you still don't get it, try printing areas.
@@TejasSameerDeshmukh Yup, what I previously understood was that if same element is considered in pse, it is giving wrong ans, but will be managed during the other element's nse. But, I just wanted to make sure my observation is correct.
A small question in the brute force approach Are we storing value of next smaller element or the index of nse ? If we are storing value , then in the above example arr = 2 1 5 6 2 3 if we take element 6 , nse would be 2 and pse would be 5 then area of 6 i.e., 6*(2-5-1) would become negative , but the actual area of that bar is 6 * 1.
Can anyone help with my code. This is giving me wrong output. I have tried two approaches. Both are not giving output properly. import java.util.*; public class Practice { public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuffer s = new StringBuffer(sc.next()); int n = sc.nextInt(); int[] a= new int[n]; for(int i=0;i a[i]) { int height = a[st.pop()]; int width = st.isEmpty() ? i : i - st.peek() - 1;
area = Math.max(area, height * width); } st.push(i); } while( !st.isEmpty()) { int height = a[st.pop()]; int width = st.isEmpty() ? a.length : a.length- st.peek() -1; area = Math.max(area, (height * width)); } return area; } private static int largeRectangle(int[] a, int n) { List nse = new ArrayList(); List pse = new ArrayList(); nse = findNSE(a); pse = findPSE(a); int maxRec = 0;
} Collections.reverse(nselis); // Reverse the list to match the original order return nselis; } private static List findPSE(int[] a) {
List pselis = new ArrayList(); Stack st = new Stack(); for(int j=0 ; j< a.length; j++) { while(!st.isEmpty() && a[st.peek()] > a[j]) st.pop(); pselis.add(st.isEmpty() ? -1 : st.peek()); st.push(j); } // No need of Reverse the list because you're already processing the array from left to right. return pselis; } }
Closed the video three times in three days , was not able to understand the approach or you can say was scared of the optimal approach and skipped the whole question many time but didn't gave up Its day 4 and now i have understood everything.
I am quite proud of myself ;-).
🎉
The Explanation for the most optimal solution is just Amazing! #GOATOFDSA
When he said "pretty simple, isn't it"! Nahi bhaiiiii!
🥲
It is.. Watch again with cool mind.. And a pen and paper..
For next or previous smaller element, in the while loop (which pops out elements), the condition we use is ">=" (greater than or equal to). Here, in the single pass approach we are using ">" (strict greater than). There are implications with duplicate elements in the input (just for fun understanding):
Consider the input is [2, 2, 2, 2]:
Case 1: If we were to take ">" (strict greater than), the area computed for each index will be 8, 6, 4 and 2 respectively. The last 2 (index 3) will be popped first and it will have the previous 2 (index 2) sitting on top of the stack, giving it an area of 2 x (4 - 2 - 1) = 2. For the next element, it will be 2 x (4 - 1 - 1) = 4, and so on.
Case 2: If we were to take ">=" (greater than or equal to), the area computed for be reversed, i.e. 2, 4, 6 and 8 respectively. The first element (index 0) will be popped first when looking at second element (index 1), giving out area = 2 x (1 - (-1) - 1) = 2. Then second element will be popped while looking at the third element, and so on.
In either case, the intermediate area computations (with duplicate elements sitting next to each other) are incorrect, because ideally in above case one would expect the area of 8 for each of the element. However, the maximum area will appear with one of the element, so we do get correct answer.
Great observation! Had a problem related to duplicates. Though someone in the comments might have mentioned it, and there you were!
The Explanation for the most optimal solution is just Amazing! Thank you
Very great intution and optimal solution is out of the box thinking
This problem is just beautiful
Reminds me how beautiful algorithms are
Yes it is indeed!
you just spoke to my heart buddy!
I saw this problem in 2019 first and tried to understand with multiple blogs and videos but couldn't understand. I understood it here. Thanks Striver
best mono stack explanation series with proper intuition, great work!
I just closed the video when I understood I have to find prev and next smaller element. But After I submitted I saw my Time and then I came back to discover that there is more to this ques !! I have solve this in one iteration !!
Damn i solved this question myself just 4 minutes in the video , brute force and optimal , Thank you Striverrrr!! Keep growing man
At first this problem appeared to be a lot intimidating but I gave time to the striver's Question description & bingo!! I cracked it to be a PSE & NSE problem, Striver🔥Thanks for building the intuition in prev lectures, guys who are coming to this video directly, plz plz first go to the next greater ele video
Broo!! Ek question tha as a begineer what can be the roadmap new question nhi ban rhe
Absolutely mind Blowing Approach
Hands down the best explanation for this problem
instead of another while loop you can also add -1 element to start and end of array and then proceed as same
class Solution {
public:
int largestRectangleArea(vector& h) {
h.insert(h.begin(),-1);
h.push_back(-1);
int n=h.size();
int maxi=-1;
stack st;
for(int i=0;ih[st.top()])st.push(i);
else{
while(!st.empty() && h[st.top()]>h[i]){
int height=h[st.top()];
int pse=0;
st.pop();
if(!st.empty())pse=st.top();
maxi=max(maxi,height*max(1,(i-pse-1)));
}
st.push(i);
}
}
return maxi;
}
};
Dry run is crazy for optimal , Just amazing , Thank you.
after watching the optimal approach multiple times in couple of days i was unable to understand it but on 5th and 6th day i watched it again and got every single bit of it understood everything completely
optimal approach dekh kr aur smjh kr maza aagaya sach mai....
amazing u r the best. I didn't even see the pseudo code just solved the problem
"pretty simple, isn't it"! this line blew my mind🫨
The optimal one is work of a genius ❤
Majedaar problem, din ki achi shuruwaad hui!!
Solved previous 3 question at own just because of Striver : ) Thank you Raj Vikramaditya Sir aka Striver #GOATOFDSA
This problem is beautiful. Beautiful things are dangerous, this is an example.
class Solution {
public:
int largestRectangleArea(vector& heights) {
stack st;
int maxArea = 0;
int n = heights.size();
for(int i = 0; i < n; i++) {
while(!st.empty() && heights[st.top()] > heights[i]) {
int element = st.top();
st.pop();
int nse = i;
int pse = st.empty() ? -1 : st.top();
maxArea = max(heights[element] * (nse - pse - 1), maxArea);
}
st.push(i);
}
while(!st.empty()) {
int nse = n;
int element = st.top();
st.pop();
int pse = st.empty() ? -1 : st.top();
maxArea = max(heights[element] * (nse - pse - 1), maxArea);
}
return maxArea;
}
};
Take it out na, why are you waiting? take it out!😂
Amazing explanation for optimal solution
Beautify explanation. I love your energy ❤❤
mind blown away #striver, after watching above algorithm. #GoatForAReason.
optimal to bahut tagda tha
Are you going to update these links in A2Z sheet ? These videos seems latest and better
Had to watch this twice to understand this.
If you are able to understand the approach 2, just watch Neetcode's explanation for the same problem and then come back to striver's explanation. You will understand the problem clearly then.
mind boggling 🤯
this is Art
great explanation.
Old video for Optimal Approach
th-cam.com/video/jC_cWLy7jSI/w-d-xo.html
You are unreal!
Isn't the time complexity of the brute force solution is O(4 * n ^ 2) ??
Thank you bhaiya ❤
I have an issue with the optimal approach. What if there is a value that is to be popped and the top value is equal to it?
Suppose the given vector is 2 3 2 1, so 2 is pushed at i = 0, then 3 is pushed at i = 1, then 3 is popped and maxarea is calculated for i = 2, there nse is 2 and pse is 0, and 2 is pushed. But then, for i = 3, before 1 is pushed 2 is popped, there is nse is 3, it's fine. But pse is becoming 0 there because s.top() is still 2, but the same height can't be pse because it is added in the width. There is my issue. Instead of pse becoming -1, here pse becomes 0.
Can someone plz explain?
You're correct. Let me try to explain. Its little intuitive.
For the 3rd element, we indeed get a wrong answer. if you print the Areas at each iteration, you can verify it. Yet the overall answer comes out to be correct, because the case ignored by this 2, is covered by 1st 2. Think about it, when you're at i=0, the max width is 3 (0,1,2 positions), and the same is at i=2; so, even if this area is not covered at i=2, it will be covered by i=0, the original guy that arrived, as for it, the right is same as the right for i=2 i.e nse = 1 at posi 3. but for i=0, pse will be still -1, which may not have been covered by i=2, but this guy covers it.
If you still don't get it, try printing areas.
@@TejasSameerDeshmukh Yup, what I previously understood was that if same element is considered in pse, it is giving wrong ans, but will be managed during the other element's nse. But, I just wanted to make sure my observation is correct.
Hats off man :)
when the interviewer don't want to hire u
A small question in the brute force approach
Are we storing value of next smaller element or the index of nse ?
If we are storing value , then in the above example
arr = 2 1 5 6 2 3
if we take element 6 , nse would be 2 and pse would be 5 then area of 6 i.e., 6*(2-5-1) would become negative , but the actual area of that bar is 6 * 1.
index
WE SHOULD STROE THE INDEXES
sir explain sum of or of all subarrays
please
#understooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood, tysm vro !!!!
pretty simple !! 😅😅
off topic but striver is so fine
padh le
UNDERSTOOOOD
15:02 why am I kicking them out🤭
why we need -1 at (nse-pse-1) can someone explain?
Thanks a lot
Hey striver, why we need to assign 'n' to nse not '-1'?
While calculating differences, Since we are playing with indices we should consider taking the size of an array instead of -1.
thanks bhaiya
UNDERSTOOD;
Aint no way we can come up with this approach in the interview
But now you can if you see a similar question, and it strikes that it requires a monotonic stack.
Wrong answer 😢
tysm sir
fkin legend
Understood
Anyone notice "wrong spelling of rectangle in thumbnail"😅
public int largestRectangleArea(int[] heights){
Stack st = new Stack();
int maxRect = 0;
int nse = 0;
int pse = 0;
int currElement = 0;
for (int i = 0; i < heights.length; i++){
while(!st.isEmpty() && heights[st.peek()] > heights[i]){
nse = i;
currElement = st.peek();
st.pop();
pse = st.isEmpty() ? -1 : st.peek();
maxRect = Math.max(maxRect,heights[currElement] * (nse - pse -1));
}
st.push(i);
}
while(!st.isEmpty()){
nse = heights.length;
currElement = st.peek();
st.pop();
pse = st.isEmpty() ? -1 : st.peek();
maxRect = Math.max(maxRect,heights[currElement] * (nse - pse - 1));
}
return maxRect;
}// Time Complexity: O(n) + O(n) = O(n)
// Space Complexity: O(n)
Spelling mistake hai thumbnail me
True sdet found here, jaldi apply kro 😂
Wow you a beauty
very bad
Can anyone help with my code. This is giving me wrong output. I have tried two approaches. Both are not giving output properly.
import java.util.*;
public class Practice {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
StringBuffer s = new StringBuffer(sc.next());
int n = sc.nextInt();
int[] a= new int[n];
for(int i=0;i a[i])
{
int height = a[st.pop()];
int width = st.isEmpty() ? i : i - st.peek() - 1;
area = Math.max(area, height * width);
}
st.push(i);
}
while( !st.isEmpty())
{
int height = a[st.pop()];
int width = st.isEmpty() ? a.length : a.length- st.peek() -1;
area = Math.max(area, (height * width));
}
return area;
}
private static int largeRectangle(int[] a, int n) {
List nse = new ArrayList();
List pse = new ArrayList();
nse = findNSE(a);
pse = findPSE(a);
int maxRec = 0;
for(int i = 0;i=0 ;j--)
{
while(!st.isEmpty() && a[st.peek()] >= a[j])
st.pop();
nselis.add(st.isEmpty() ? a.length : st.peek());
st.push(j);
}
Collections.reverse(nselis); // Reverse the list to match the original order
return nselis;
}
private static List findPSE(int[] a) {
List pselis = new ArrayList();
Stack st = new Stack();
for(int j=0 ; j< a.length; j++)
{
while(!st.isEmpty() && a[st.peek()] > a[j])
st.pop();
pselis.add(st.isEmpty() ? -1 : st.peek());
st.push(j);
}
// No need of Reverse the list because you're already processing the array from left to right.
return pselis;
}
}
how the hell you even think of solution like the optimal one crazy dude! respect for those who can do it🫡
Mind got tricked, but also get back to it's original way upon listening his mind blowing approach. 🫡
is it easy to think of the optimal solution for a coder doing dsa over months? 🥲
Understood
Understood