Largest Area Histogram | Solution
Vložit
- čas přidán 18. 04. 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we explain the solution of the problem Largest Area Histogram. To understand the question, click here: • Largest Area Histogram...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#pepcoding #programming #coding
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Sir, you are so calm while explaining even each smallest point..appreciation and gratitude to most heights..
Thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Best explanation ever. Now I realized why you recommend thinking about other variations of the next greater element on right using stack video.
And this is the correct way to explain
Thankyou so much
arr[i]
For,Same hight...it should pop the element otherwise it will insert boundry of same hight.
last minute me correct kiya h
Sir it was a bit complex, but your dry run, is like ..... fab
This is perhaps the best explaination out there for this question. Thanks a ton sir, subscribing to your channel now !!!
Thanks for the sub!
Thank you, I missed some of the stack part, but the overall video is the best.
Sir, I had read the solution to this question from many sites but never manage to learn this concept but your videos are great sir. AWESOME>>>>>>>>>>>>>>>>>>>... ThankYou Sir.
Keep watching. Will you also like to drop us a review?
Really good and thank you very much for your easy explanation
For test case [2,4].The array will overflow.So push arr.length - 1 to the stack instead of arr.length initially while filling rb.
was struggling to form mono stack , thanks for explaining the code
Thank you so much sir.
Thank you 🙏
Sir U deserve millions of subscribers. I think you are the best on youtube.
Amazing explanation
very nice question ! ekdum pyara sa sawal !
Thankyou beta!
I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc
thanks sir, nice explanation but it is not working for long long data types. getting segmentation fault because we are using 3 arrays and 1stack. and also other variables of long long data types
I really enjoyed the explain from this video. However, I tried the same approach on leetcode but it failed for cases where there are multiple contagious duplicates like 11111 or 11112222. In both the while loops the conditions should be arr[i]
thank u good sir
Sir, same code line no 46, if lb[i] = n;
then also it gives 10/10 did it mistakenly but unsterstood
Stack queue m bdi tgde sawal h, Thanku sir
All the best
Sir, you just made it a piece of cake. Thank you for this crystal clear explaination!🙌🙌
Thank you so much, We are glad that it could be helpful. For better experience visit on nados.pepcoding.com
Also follow our Instagram account to stay tuned.
instagram.com/pepcoding/
@@Pepcoding meri dadi bhi aapka channel dekhti hai
@@vinamrasangal8436 ab dadi bnegi coder🤣
class Solution {
public int largestRectangleArea(int[] arr) {
int n= arr.length;
int[] lb= new int[n]; //next smaller element on left
int[] rb= new int[n]; //next smaller element on right
//calculate rb using stack
Stack s= new Stack();
rb[n-1]=n; s.push(n-1);
for(int i=n-2; i>=0; i--)
{
while(!s.isEmpty() && arr[i]
thanku
thanks sir so much...
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Wonderful Explanation sir
Thankyou beta!
Will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms)
By far the best explanation !!
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding Sure sir, more than happy to do it 🙂
Fantastic explanation sir..
But u are not considering equal hights.
Best DSA course on CZcams
Please visit nados.pecoding.com for more such amazing content :)
Sir my outputs are always giving an error "Exception in thread 'main'Java. Lang. Array". Can sir or anyone please me out? Plz sir!
ek no. explanation bhaii
Shukriya ji🙏
did this one using alternate approach for both boundaries ...... but what shoud be the default approach??
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. Therefore, we have a premium facility available for the students in which you can get the 12 hours doubt support facility. Jisme aap agr kisi bhi question main kahin bhi faste ho to aap doubt support par reach kar skte ho aur aapko TA assign ho jayega and you can get your doubt resolved from them.
Sir your explanation is really good
Keep watching and for better experience and well organised content sign up on nados.io and start learning.
Awesome explanation sir
Glad you liked it!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
11:36 bhari sambhavna hai 😂😂 sir your teaching is on Baap level 😎
How its time complexity is O(N) ?
Love you sir
Love from Pepcoding, for better experience and well organised content sign up on nados.io
wont work for test case int ar[] = {1,1,1,1,1}; unless you do ar[s.top()] >= ar[i], Correction is copmparision should be >= . everything else is great.
sir, we were expected to push index , you have mistakenly pushed values while dry run. (code is correct) 15:15
This is the best expalination Thank you very much sir please keep making such solution videos loved it :)
Sir ❤️❤️❤️
u r awesome... the way u explain is so calm n relaxing😇😇
Thank you so much 😀 Keep learning, Keep growing and keep loving Pepcoding!😊
Sir , if given input is in the form of a String("6 , 2 , 5 , 4 , 5 , 1 , 6") , then how we can solve this problem by using the same concept.
string ko split karo, array milega strings ka, har element ko integer mei convert karo.
@@Pepcoding Thank you sir...😊
sir at 2:19 apne kha ki n^2 ka time hojayega lekin last me O(n) ka hogya ....approach ache se amaj aagye lekin yeah time complexity samaj nhi are isme ,,.. @pepcoding
beta ek baar next greater element dekhie
ok sir
sir,why we write arr[i]
because hum stack mein index add kr rahe hai...value nhi..
are we taking two stacks in this question.??..one for right boundary and one for left boundary
no
yes. There are 2 stacks being created
No we are using 2 arrays which sir has declared on the line 17 and 28 rb and lb .
Sir your way of explaining things is next level 😍😍
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
@@Pepcoding done sir 5⭐
I think we should remove element that is equal and grater than current element. Test Case [6,4,5,4,7]
Guys he updated the test cases and corrected the = case.
for(int i = 0 ; i= 0 && a[left] >= a[i] ) {
leftcount+=1 ;
left-=1 ;
}
while(right < n && a[right] >= a[i] ) {
rightcount += 1 ;
right+=1 ;
}
max = Math.max(max , (leftcount + rightcount + 1) *a[i] ) ;
}
System.out.println(max) ;
sir wht is the time complexity of this solution??
beta O(n)
Best teacher 🔥
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
There is an audio delay in the video
i think sir there is some problem with the voice of the video
Great explanation 👌👌👌
Thank you ji
Instead of arr[i] < arr[st.peek()] it should be arr[i]
Correct
no this condition does not apply this problem becoz it give error in leetcode and gfg.
Good catch
{1,1} now passing test case for this {1,1,1} also
Yes Exactly .
Sir please provide the code also..
code is available on pepcoding website..under solution of this question
pura lecture 40 % samj aya but dry run 100 % samj aagaya
can anyone code this in python
Leetcode 84
Leetcode 84
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = Integer.MIN_VALUE;
int[] lb = new int[heights.length]; // next smaller element to left
Stack st = new Stack();
st.push(0);
lb[0] = -1;
for (int i = 1; i < heights.length; i++) {
while (st.size() > 0 && heights[st.peek()] >= heights[i]) {
st.pop();
}
if (st.size() == 0) {
lb[i] = -1;
} else {
lb[i] = st.peek();
}
st.push(i);
}
st = new Stack();
int[] rb = new int[heights.length];
rb[rb.length - 1] = heights.length;
st.push(heights.length - 1);
for (int i = heights.length - 2; i >= 0; i--) {
while (st.size() > 0 && heights[st.peek()] >= heights[i]) {
st.pop();
}
if (st.size() == 0) {
rb[i] = heights.length;
} else {
rb[i] = st.peek();
}
st.push(i);
}
// for (int val : lb) {
// System.out.print(val + " ");
// }
// System.out.println();
// for (int val : rb) {
// System.out.print(val + " ");
// }
// System.out.println();
for (int i = 0; i < heights.length; i++) {
int width = rb[i] - lb[i] - 1;
int area = width * heights[i];
if (area > maxArea) {
maxArea = area;
}
}
return maxArea;
}
}
class Solution {
public int largestRectangleArea(int[] arr) {
int[] rb = new int[arr.length];
Stack st = new Stack();
st.push(arr.length-1);
rb[arr.length-1] = arr.length;
for(int i=arr.length-2;i>=0;i--){
while(st.size()>0 && arr[i]
i think voice and video syncing mismatch
Was hectic till dry run started then all sorted 👌
Taliya bajti raheni chahiye..
Watch last minute of this video if your test cases are failing
answer to 12 aana chaiye na compiler me 16 kyu dikha rha hai?
can anyone help me with this
Wo -1 krna bhul gye.....width= right-left-1
Sir sirf yhi q ne pura din mera consume kar lia
6q per day ka target nhi ho pata aese questions ki wajah se
Please guide
yaar yeh waali technique level up waale course Mein use karna abhi foundation mein dhang se samjho ki kaise type ke questions hote hai ek particular topic ke
@@saarimkhan557 sir agr kuch q smjh toh ate hai but code nhi hore so problem toh nhi hogi naa
i will definitely try in next videis
@@harshpandey7605 just try and try ,waise mai sir nhi hoon 😅
@@saarimkhan557 Aree nevermind
B
bro you can do one thing , set a target of giving at max 15 min , if you still find it difficult , see the solution vedio upto that point jahan sir logic samjha rahe hote hain and try to code it on eclipse. jab lage ki pura solution acche dekh liya aur samajh aa gaya hai move on and write a complete in your note book explaning the appproach in most detail manner. after one day or two, pick a simmilar qtn and try slving it. iss tareke se logic dimag mei baith jayega aur tabh bhi nahi hoga to matlab tum ne ratta mara tha, to dobara samjh lo, keep hustling, keep coding
For Input:
5
1 2 3 4 5
This code is not giving correct output for this input , please make correction in code.
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
@@Pepcoding I know you can't solve my doubt. I am just informing you nothing else.
@@shivanigupta_19 the correct output for the given input is 9, and the code gives the same output.
Please correct me if I am wrong.
above code and logic is failing for the test case : 11 11 10 10 10
okay, will check
@@Pepcoding did it work??
ofc it will fail, arr[i] < arr[st.peek()] , just change this part to arr[i]
@@GannaJuiceEnthusiast I tried even that, but it still fails. Please check my comment above
Wrong Answer
Details
Input
[1,1]
Output
1
Expected
2
not good solution so confusing...
code for leet code 84 --
public static class Pair {
int index, val;
public Pair(int index, int val) {
this.index = index;
this.val = val;
}
}
public int largestRectangleArea(int[] heights) {
int immediateSmaller2Right[] = new int[heights.length];
int immediateSmaller2Left[] = new int[heights.length];
immediateSmaller2Right[heights.length - 1] = heights.length;
immediateSmaller2Left[0] = -1;
Stack st = new Stack();
st.push(new Pair(heights.length - 1, heights[heights.length - 1]));
for (int i = heights.length - 2; i >= 0; i--) {
while (!st.isEmpty() && st.peek().val >= heights[i]) {
st.pop();
}
if (st.isEmpty()) {
immediateSmaller2Right[i] = heights.length;
} else {
immediateSmaller2Right[i] = st.peek().index;
}
st.push(new Pair(i, heights[i]));
}
st = new Stack();
st.push(new Pair(0, heights[0]));
for (int i = 1; i < heights.length; i++) {
while (!st.isEmpty() && st.peek().val >= heights[i]) {
st.pop();
}
if (st.isEmpty()) {
immediateSmaller2Left[i] = -1;
} else {
immediateSmaller2Left[i] = st.peek().index;
}
st.push(new Pair(i, heights[i]));
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < heights.length; i++) {
max = Math.max(max, heights[i] * (immediateSmaller2Right[i] - immediateSmaller2Left[i] - 1));
}
return max;
}
I think you should use
while(!st.empty() && heights[i]
correct then it passes all the test cases