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 ;-).
I struggled for at least 45 minutes to get the Brute Code done by myself. I thought that is the most optimal. I am amazed at how someone's thought process can go to such a huge extent. This is an absolute Genius of you Striver. Hats Off!!!!!
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 !!
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....
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
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 ;-).
🎉
same
The Explanation for the most optimal solution is just Amazing! #GOATOFDSA
I struggled for at least 45 minutes to get the Brute Code done by myself. I thought that is the most optimal. I am amazed at how someone's thought process can go to such a huge extent. This is an absolute Genius of you Striver. Hats Off!!!!!
This guy's existence is so important for my brain to evolve as a coder :)
When he said "pretty simple, isn't it"! Nahi bhaiiiii!
🥲
It is.. Watch again with cool mind.. And a pen and paper..
The Explanation for the most optimal solution is just Amazing! Thank you
best mono stack explanation series with proper intuition, great work!
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
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!
finally after 5 days of stressing out on this problem undeerstood the concept , man this guy is genius and i am thankfull to you man😊
🤣
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!
Damn i solved this question myself just 4 minutes in the video , brute force and optimal , Thank you Striverrrr!! Keep growing man
amazing u r the best. I didn't even see the pseudo code just solved the problem
i cannot unsertand the intuition for optimal solution at first , after spending lot of time i got it thank u so much for u r videos😍
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 !!
Absolutely mind Blowing Approach
Dry run is crazy for optimal , Just amazing , Thank you.
The optimal one is work of a genius ❤
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;
}
};
Thanks for nse, pse approach before optimised !
Couldn't understand the optimised directly 😃
Best Explanation🎉✨
"pretty simple, isn't it"! this line blew my mind🫨
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....
Majedaar problem, din ki achi shuruwaad hui!!
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
@@seffsef6301 just keep practice the same question again after week, so you can develop the institution.
Thanks for providing a brief explanation on this
Solved previous 3 question at own just because of Striver : ) Thank you Raj Vikramaditya Sir aka Striver #GOATOFDSA
veryy well explained ❤ thank you soo much sir🙏🏻
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;
}
};
This problem is beautiful. Beautiful things are dangerous, this is an example.
Beautify explanation. I love your energy ❤❤
Take it out na, why are you waiting? take it out!😂
mind blown away #striver, after watching above algorithm. #GoatForAReason.
Amazing explanation for optimal solution
You are unreal!
mind boggling 🤯
this is Art
Hats off man :)
Are you going to update these links in A2Z sheet ? These videos seems latest and better
optimal to bahut tagda tha
Had to watch this twice to understand this.
great explanation.
Thank you bhaiya ❤
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.
UNDERSTOOOOD
#understooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood, tysm vro !!!!
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.
Isn't the time complexity of the brute force solution is O(4 * n ^ 2) ??
Thanks a lot
No way anyones coming up with the optimal approach in an interview, phew..
UNDERSTOOD;
thanks bhaiya
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
when the interviewer don't want to hire u
sir explain sum of or of all subarrays
please
off topic but striver is so fine
padh le
pretty simple !! 😅😅
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.
why we need -1 at (nse-pse-1) can someone explain?
tysm sir
Understood
fkin legend
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.
15:02 why am I kicking them out🤭
Anyone notice "wrong spelling of rectangle in thumbnail"😅
26:20 OHH HELL NAHH!!
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)
Wrong answer 😢
Wow you a beauty
class Solution {
public:
void PSE(vector& heights , vector& pse){
stack st;
for (int i=0 ; i= heights[i]){
st.pop();
}
if (!st.empty()) pse[i] = st.top();
st.push(i);
}
}
void NSE(vector& heights , vector& nse){
stack st;
for (int i=heights.size() - 1 ; i>=0 ; i--){
while (!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
if (!st.empty()) nse[i] = st.top();
st.push(i);
}
}
int largestRectangleArea(vector& heights) {
int n = heights.size();
vector pse(n , -1);
vector nse(n , n);
PSE(heights , pse);
NSE(heights , nse);
int answer = INT_MIN;
for (int i=0 ; i
Old video for Optimal Approach
ua-cam.com/video/jC_cWLy7jSI/v-deo.html
Spelling mistake hai thumbnail me
True sdet found here, jaldi apply kro 😂
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
Understood