Largest Area under Histogram efficient algorithm using Stack | Coding Interview Question
Вставка
- Опубліковано 5 жов 2024
- How to find out the largest area under Histogram in a Stack ? Learn to solve in this tutorial :)
For more online courses visit - www.codingblock...
Check courses on - online.codingbl... [Free Trial Available]
Coding Blocks is pleased to announce courses like C++ and Java, Data Structures and Algorithms, Web and Android Development(Java and Kotlin), Competitive Programming, Coding Interview Preparation and Machine Learning, AI and more.
#CodingBlocks #ProgrammingMadeEasy #LearnCodingOnline
Like our FaceBook Page - / codingblocksindia
Follow us on Instagram - / codingblocks
Follow us on Twitter - / codingblocksin
Source code available on -github.com/cod...
For more interesting tutorials - / @codingblocksindia
I went through atleast a few videos before giving this one a try and boy, it was completely worth it. The explanation with a running example, just superb. Kudos to the team!
This is the best explanation I have ever seen about any question. Everyone is running behind codes but no one is talking about mathematics behind that. I have seen a lot of videos related to this but did not satisfy. But now I am fully confident in these problems. Thank you so much , you always use to explain hard problems in quite easy manner .
I don't know why so many ppl downvote this excellent presentation , this is best explanation I found, rather than other videos which just show the formula and conclusion only. Thanks for the detailed illustration
The best explanation so far. I am still lagging behind on the intuition, but now I can prove the algorithm by induction.
Finally an explanation that makes sense!
The only explanation on youtube for this problem which makes sense.
Expressing my gratitude to everyone who made creation of this video possible.A really simple ,thorough and good explanation.
Thanks Vansh !!
the approach was nice, I liked the explanation with a proper example, Just one suggestion: please remove double logos from the bottom right corner.
Dude, you saved my day. all the remaining videos were a waste of time. 🤔 I wonder how the hell did the first person who solved this question in the world got this idea or thought of this algorithm. It's just amazing 🤯
He must have been a genius...
I feel the same for the person who designed this problem.
Finally got it after going through so many videos.
I still have no idea how someone gets idea to use stack for this problem
@@venuvenu2719 Yes, I'm thinking the same :(
Very nice explanation
Now i got the intution behind this!
best explanation thanks
Best solution to this problem among all videos
Now I am able to understand the logic, thanks
Honestly very nice explanation.
easiest explanation so far.Keep making such videos.
I found your explanation confusing because the first step you explained was that you would only push an index onto the stack if the height is larger than the previous height, but then you went on to push literally every single element into the stack regardless of its height comparison with the previous height.
The best and simplest explanation.
Woow what a worthy explanation:-) only now I am able to get the intuition of this problem
Great. Keep Learning with Coding Blocks!
Thank you so much , finally I understand the intuition behind this algorithm :))
You just ammmazingly explained.
Thanks💕
best video so far on this topic.
best explanation ever
Very nice lecture...... always upload this type of lectures bro.this will more helpful to us
Check out complete course at online.codingblocks.com
But what if the numbers are in increasing order e.g. 1,2,3,4,5 ?
Set the speed to 1.25 or 1.5 and thank me later.
The video was a lot better than others made on similar topic , yet you would have to develop the intuition on your own .
Best explanation.....even better than geeksforgeeks
very well explained
thank you so much
Thank you very much for the explanation. Now I finally understood this question! Subscribed!
Thank you so much !!
I really appreciate what you did here. Amazing work and such explanation was missing in others. I encourage to put out more video and keep up the good work.
its long but definitely worth it
That's what she said :p
@@sachingarg4385 :)
Thanks for this video. Nice Explanation. Where is the video or the link to the code ?
Thank You Coding Blocks.
Nice explanation. Thanks!
Amazing explanation loved it! Scroll to 13:41
what if bar's are in increasing order eg -> 1, 2, 4, 5, 6, 7
It will be the worst case scenario for this algo with O(2n) complexity.
We can add 0 at the end of the array.
This is one hell of a notorious problem I have ever seen and the most fabulous explanation given for it :)
best explanation..Thanks
@ 7:46 you explained [R-L-1] * hight of the minimum current bar popped from stack , again in the diagram L = 0 and R=4 then its [4-0-1]*3 = 9 right .. and why there is extra -1 in the formula [R-L-1] , also i understood L and R bars height is less than the current bar popped up from the stack please explain this point , apart from this every thing is understood
If index 4 is the right hinderance and 0 index is the left hinderance. Then the rectangle consists of indexes 1, 2 & 3. Hence (R-L) -1 i.e. (4-0)-1 as the left is not inclusive, it is the hinderance before the last bar. Hope this helps
By far the best video on this problem. Kudos _/\_
Thanks!! Do Subscribe for more such videos
Glad to see so many paid comments here
I actually like their explanation ,but this is one of the worst explanation I have ever seen
Thanks a lot..grt explanation..excellent work!!
Example is same as in GFG article
Very good Explination
explanation starts at 11:00 and it is great
thanks bro
WHAT IF THE CURRENT NUMBER IS EQUAL TO THE TOP OF THE STACK???????
Thnax man...really helpful!! keep it up!
7:45 Area = (R - L - 1) * Height of current bar, So It should be, Area = (4 - 0 - 1 ) * 3 ?
Yes you are r8...He has written that by mistake...
Finally I understood it
Glad you liked our video.
Thanks a lot ! I was able to follow through and wrote the code myself. Best explaining video so far on this problem
Thanks Glang for the compliment. please subscribe for more such videos.
For O(n^2) solution, how would I be able to know that what is the minimum height bar in (i, j) range ? at 2:30
My solution
#include
using namespace std;
int local_min(int arr[],int i,int j)
{
int min=arr[i];
for(int p=i+1;parr[p])
min=arr[p];
}
return min;
}
int main()
{
int arr[]={6,2,5,4,5,1,6};
int n=7;
int area=0;
for(int i=0;i
// Largest area under histogram
// O(n^2)
#include
#include
using namespace std;
int histogram(int a[],int n)
{
int min,area,i,j,ans=0;
for(i=0;in;
for(i=0;i>a[i];
cout
Please add code section in description.
very good eplanation bt initial 10mins are boring.
Sir, I didn't find this type of video. Extraordinary ,,super,,
How to open the source code on GitHub
please provide the code as well
great explanation once again!!!!!!!!!
Thanks Manish
* shows gratitude *
Thanks Sir...
I coded according to your algorithm...ideone.com/LjOjXm (my solution) but in www.spoj.com/problems/HISTOGRA/ its giving tle....pls help
Thanks a lot :)
can u please prove us the code?
You just can't do this on your own right?
This is not any valid reason that pop and push only once make it O(n)
wow!
Aaaand.... what is the real-world use case of this? Why would i need this?
0:26
Ok
watch at *1.5, your welcome!
thenks.
nice
came here with some expectations , explanation is not good i didn't understand any part of it
worth watch for 30 mins !
i don't understand anything
What if the first bar is of 100 units alone.
Its own area will be 100*1=100
so many ads
Thanks for the useful video, but, man, I never heard such a monotonous voice drawing out it's words in such a dull and languid way. Sheesh!
Thanks for making your video but your area calculation creates too much magic. If you code this you will find your containers are missing important data. Using a stack you need to keep the height as well as the valid starting point. Using your example the data would look like these pairs (6,0),(2,1),(5,2),(4,2),(1,0),(6,6). It would be to your benefit to code this before teaching/explaining to others. Here's a test case I used : {2,6,3,2,5,5,5,4,4,5,1,7}. Happy Hacking!
Explanation is outstanding keep it up bro👍