Largest Rectangle in Histogram | Part - 1 | Leetcode 84
Vložit
- čas přidán 7. 08. 2024
- Check out website: SDE sheet: bit.ly/takeUforward_SDE
Pre-req: • Next Greater Element |...
Part-2: • Largest Rectangle in H...
Watch at 1.25x for better experience ..
Visit Relevel: relvl.co/vcd
upGrad(BD)- relvl.co/eh5
Urban Company(BD)- relvl.co/5w0
Vedantu(BD)- relvl.co/h3t
Curefit(BD- relvl.co/d08
Cred(FD)- relvl.co/fqa
Digit(FD)- relvl.co/0vy
Razorpay(BE)- relvl.co/fly
Yellow Messenger(BE)- relvl.co/wu9
Cred(BE)- relvl.co/y0h
1mg(BE)- relvl.co/3x7
Digit(BE)- relvl.co/wkz
---------------------------------------------------------------------------------------------------------------------------
Problem Link: leetcode.com/problems/largest...
C++/Java Code: takeuforward.org/data-structu...
---------------------------------------------------------------------------------------------------------------------------
✅Use coupon-code "STRIVER" for getting 10% on all subscriptions of Unacademy
✅Use coupon-code "TAKEUFORWARD" for getting 15% for all CN courses: aff.codingninjas.com/click?o=...
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
✅Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
---------------------------------------------------------------------------------------------------------------------------
Products that I use:
Best Mic in Affordable Range: amzn.to/3hiTr9p
Yeti mic: amzn.to/3dL4tDF
Boya mic: amzn.to/3h4ROgy
Logitech webcam: amzn.to/3h7d2KI
Cooling pad: amzn.to/3y46pi4
Wacom pad: amzn.to/3xacSIq
Ring light: amzn.to/3y7aaU1
Mic Arm Stand: amzn.to/3qzMuFa
Digitek Green light stand: amzn.to/2U7B3bI
Digitek Stand: amzn.to/363m7Oo
Tripod: amzn.to/35ZmbyT
Office chair: amzn.to/3qysu5Z
Ipad Air: amzn.to/3hjpiXx
Iphone 12: amzn.to/3AavyJV
Watch: amzn.to/3hn7w5A
Macbook Air: amzn.to/363lSTu
Macbook Pro: amzn.to/3qCczDr
Board: amzn.to/3x8GLIO
Mouse: amzn.to/360Asv1
---------------------------------------------------------------------------------------------------------------------------
✅Placement Series: • Let's give back to the...
✅Placement Series (Arrays, Sorting..): • C++ and Java |Brute-Be...
✅Hashing Playlist: • Two Sum Problem | Leet...
✅Greedy Playlist: • N meetings In One Room...
✅Recursion Playlist: • L8. Combination Sum | ...
✅Graph Playlist: • 3 MAJOR ANNOUNCEMENTS ...
✅Two Pointer Playlist: • 3 SUM | Brute | Better...
✅Binary Search Playlist: • Nth Root of a Number U...
✅LinkedList Playlist: • Reverse a Linked List ...
✅Advanced DS playlist: • Fenwick Tree Tutorial ...
✅Stack&Queue Playlist: • Implementation of Stac...
✅Greedy Algorithms: • N meetings In One Room...
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: /
✅ Instagram: /
✅Connect with us: www.google.com/search?client=... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
##dsa #striver #leetcode
Thank you for such amazing explanation. I cant find a single video of others who explain with such clarity. No matter who criticize you continue the work u r doing.
One thing I want to point out is that, in interview, there are some scenarios when only brute force solution exists to the given problem. And its important to understand that even though solution is not optimal, it has given the solution indeed. So, optimal solution is not always guaranteed, even though it exists in this problem.
Nevertheless, great video @takeUforward, the best explanation for this problem I found so far. 🤟
yes, I am just bothered with too much to remember - formula and technique :(
I saw multiple videos on this question, but this one made it clear. Thank you so much.
Wish i could like it millions of time❤️
Never have I ever seen such a great video❤️
Superb explanation 👍
Tried your best to embibe intuition👍❤️
❤️ from IIT Bombay. Nice Work!!
Hum log Mtech wale hai , hame dekhna padta hai :}
Or bhai kaha lgi placement
@@manasgotefode bhai usse shadi karoge kya?
Flex karne ka tareeka thoda kezual hai
bhai the energy with which u explain incredibly amazing!
Thanks Striver for such a neat explanation. Intuition is to store next smaller and previous smaller value(here index) for current value in two separate arrays and then use this approx formula currentHeight * (currentNextSmallerValue - currentPreviousSmallerValue) for current index. Take the max out of this to get desired output
Really liked the intuition you developed with boundaries. Thoroughly impressed by the way you have explained this problem. I solved this problem using the boundary approach you mentioned :). Pretty nice explanation as I can imagine its hard to put this complex a thought into appropriate words.
There is a part-2 as well
00:01 Understanding how to find the largest rectangle area in a histogram.
02:09 Selecting the maximum area rectangle in histogram
05:43 Calculating the area of rectangles with different heights and consecutive widths.
07:44 Discussing how to find the largest area of a histogram by considering different heights and widths
11:59 Brute force solution has O(n^2) complexity
13:50 Using a stack to find left smaller boundary indexes
17:30 Identifying left smaller elements and calculating boundaries in a histogram.
19:15 Computing left and right smaller indexes using a stack
22:45 Compute the largest rectangular area in histogram
24:34 Using stack method to find left smaller and right smaller, leading to largest rectangular area.
27:53 Using stack to find left and right smaller elements for histograms.
29:27 Optimal solution explained using a 6-line code and single pass of left smaller to find maximum rectangle area
just solved before video got released now this masterpiece comes thanks for efforts sir
Here is the complete optimized algorithm...
1. create a stack st that will store indexes
2. create two arrays left_smaller and right_smaller that will store leftmost smaller and rightmost smaller index for an index i respectively.
// calculate left smaller...
3. for every arr[i]:
i. curr_height = arr[i]
// stack_top_height means arr[st.top()]
ii. while stack is not empty and stack_top_height >= curr_height:
-> stack.pop()
iii. if stack is empty left_smaller[i] = 0
else left_smaller[i] = st.top() + 1
iv. st.push(i);
end for loop
4. clear stack for reuse
// calculate right smaller...this time traverse from the back..
5. for every arr[i]
i. curr_height = arr[i]
ii. while stack is not empty and stack_top_height >= curr_height:
stack.pop()
iii. if stack is empty right_smaller[i] = n-1
else right_smaller[i] = st.top() - 1
iv. st.push(i)
end for loop
6. max_area = INT_MIN
7. for every arr[i]
i. curr_height = arr[i]
ii. width = (right_smaller[i] - left_smaller[i] + 1)
iii. max_area = max(max_area, curr_height * width)
end for loop
8. return max_area
Any feedback will be appreciated
👏
you are a diamond ... no one can replace you bro ... .
Great job! You explain every concept so easily.....
best. Liked the way to optimize the brute force. Other youtuber just directly jump on optimal solution.
You are the best! Thanks for all the efforts :)
Great explanation..learned the concept of next smaller/greater 🔥
Best Explanation, Hats off to the efforts. Subscribed !!!
UNDERSTOOD.......Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Amazing explanation man!! Coded the brute-force myself after just watching the 1/3rd of the video. You're doing god's work!!
Bhaiya you teaching is really fabulous .
I enjoy learning from your videos.
That T-shirt lol! But keep up with the good work, you explain shit very well!
Amazing explanation, thank you very much!!
The solution is well explained.
Also, please add this shirt to your merchandise collection.
Best explanation...maja aa gya 😅🤟
Thank you for this great explanation!!!
The best explanation found!!..............
Thanks striver for the wonderful explanation
Thank you much for making this video.
Striver The Real OG !! Period : )
Happy Guru Purnima @StriverBhaiya, our Guru and Inspiration ... from the day I started watching your videos ... problem solving has became easy and damn interesting :),
Your Vlogs and Lifestyle are really nice and for us a threshold...pushing us to give our best...
Lots of Best Wishes And More Success to you...
.
.
.
.
.
Date: Tera Saath (13/7) hai to...hume kya kami hai...dsa v ab hume asan lag rahi h XD XD XD
9:27 enjoy.
btw great video as usual.
crisp and clear!
Anyone who is not able to understand the solution....I would highly recommend aditya verma's solution ....THAT MAN IS A GOD
How to get logic of sub problems in mind ? The moment you told next greater element at 13:05 . I immediately got the idea how to solve and got AC in one go as I had solve next greater element problem. But "how do we get that sub concept at right time? "
Can we do this in a single traversal?
There are solutions in Leetcode Discuss with 1 traversal, but could not understand.
Best explanation video ever!!!
Superb Explanation Bhaiya 👌👌👌👌
striver bhai tum bhot mast kam krta hain....
what a great explanation!
Superb explanation ....
GOD LEVEL! THANK YOU!
Can we do sorting and take product of each element and number of remaining elements . It can be done in one loop
Best explanation!!!!
great explanation!
superb explanation bruh
This assumes you have smaller on both left and right but you aren’t always going to expect that. You can have increasing from left to right or decreasing from left to right.
such a nice explaination
Thanks for the detailed explanation!!
Is there a playlist of the leetcode solutions on your channel?
Thanks Striver for yet another amazing video!!!
Just a question :
Can another brute force approach be finding the area for each combination possible? Like so below:
public int largestRectangleArea(int[] heights) {
int maxArea = Integer.MIN_VALUE;
for(int i = 0; i < heights.length; i++) {
int min = heights[i];
for(int j = i; j < heights.length; j++) {
min = Math.min(min, heights[j]);
int area = min * (j-i+1);
maxArea = Math.max(area, maxArea);
}
}
return maxArea;
}
understood, thanks
thank you
Wah Arnab Wah ❤
Nicee T-Shirtt!!!!!
Why in the second example did you exclude the the first bar ? 1x5=5 why isn’t it 1x6?
Thank You !!
Brilliant thanks
Part 2 - czcams.com/video/jC_cWLy7jSI/video.html&ab_channel=takeUforward
Thanks bhaiya for making this video
Rider doing good. Thanks
thank you very much!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
indeed helpful
The link you have provided for part2 is the link of Part 1 .reverify it.
loved the video
Amazing
Man thank you !
18:21 Is this just me who listened to some other noise here
understood!!
Thanks!
we can also take 1 * 6 as 6 as height than also we will get rectangle whose area is maximum
Man this question is crazy
understood❤❤❤
understood
awesome!!
Understood ❤❤❤ watching in 2024!
July 1st
it's good that u try explain each and every part but u can make it more shorter it saves time
after all ek do vaar dry run karne se samaj to a he jata hai
Actually point is sb k lie h video. Bht log aise bhi hote h jinhe pura chye detailed. So for people who don’t want detailed they can fast forward na. But if i trim, then the other guys will not understand
Indeed
Just doing the same question.....and video aagyi 😂😂😂 ye mehaz itedaaq h ya khuda ka ishara🌸
Bro thanks for the video.I got total clarity after watching this.But the java code which u have given is not executing.
🔥🔥🔥🔥🔥🔥 best
Thanks a lot 🤞💯💯💯💯
understood sir
can we solve this using doubly linked list?
bhai itna stress mat diya karo, over ho jata hai kya !
heath ka dhyyan rakkho😄
height of instagram..lol .actually this indicates i am listening so carefully 😋
Super 💥💥
the link in the description is pointing to the same video not part 2
Understood!
Understood !!!!!
Ain't no way nobody's talking about the fire shirt
Understood
best
nice tshirt
Understood🙂🙂
oo bhaii maja aagya
what if there is some rectangle with zero height at middle? giving 0 when stack is empty wont work right?
Without taking that, we will consider the other rectangle..
Veeresh, even though it takes some other left_min, right_min this particular rectangle won't be considered because (right-left) * 0 (Height). so always this would be 0 and won't be considered in the max space.. correct me if I'm wrong
it's giving segmentation fault in gfg, Anyone else?
Thanks in advance :)
Getting runtime error segmentation fault error for the Same code in GFG.
Expected time complexity : O(N)
Expected Space complexity:O(N)
same ,any idea how to correct it?
actual video starts at 8:46
9:28 what was that bro🤣🤣🤣🤣
Why are you concern about greater element in the stack? Please reply..........
because a bigger histogram / building / block is something ith element can expand into, but it cannot expand into a smaller one
Understood striver