Largest Rectangle in Histogram | Part - 1 | Leetcode 84

[@divyagupta6854]

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. 🤟

[@bhagyashri7729]

yes, I am just bothered with too much to remember - formula and technique :(

[@manojnavinjamuri5867]

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.

[@nonamenoname2801-xj5]

Anyone who is not able to understand the solution....I would highly recommend aditya verma's solution ....THAT MAN IS A GOD

[@stutisuchak4525]

I saw multiple videos on this question, but this one made it clear. Thank you so much.

[@localhost_3000]

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

[@sahityavatturi121]

👏

[@nihalsingh6233]

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

[@mukeshmahajan1586]

bhai the energy with which u explain incredibly amazing!

[@thisisankitgaur]

❤️ from IIT Bombay. Nice Work!!

[@trojanhorse8278]

Hum log Mtech wale hai , hame dekhna padta hai :}

[@Aditya-m4r6v]

Or bhai kaha lgi placement

[@phantomhawk489]

​@@Aditya-m4r6v bhai usse shadi karoge kya?

[@MPrachiShinde]

Flex karne ka tareeka thoda kezual hai

[@ankitsablok952]

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.

[@takeUforward]

There is a part-2 as well

[@akshyagarg2398]

best. Liked the way to optimize the brute force. Other youtuber just directly jump on optimal solution.

[@anshuljain1700]

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👍❤️

[@DeepakKumar-yc9hr]

you are a diamond ... no one can replace you bro ... .

[@stith_pragya]

UNDERSTOOD.......Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@susrandomguy]

9:27 enjoy. btw great video as usual.

[@prabhakaran5542]

Understood ❤❤❤ watching in 2024!

[@prabhakaran5542]

July 1st

[@sandeshkumarchandrakar1622]

just solved before video got released now this masterpiece comes thanks for efforts sir

[@narendrakumariitb]

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

[@yashkumardhawan6961]

The solution is well explained. Also, please add this shirt to your merchandise collection.

[@nehasingh8181]

Great job! You explain every concept so easily.....

[@sunnykumarpal9679]

Bhaiya you teaching is really fabulous . I enjoy learning from your videos.

[@prateekshrivastava2802]

Striver The Real OG !! Period : )

[@AshishKumar-pq6pr]

Best explanation...maja aa gya 😅🤟

[@hell-o8470]

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? "

[@rydmerlin]

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.

[@teacup1431]

Can we do sorting and take product of each element and number of remaining elements . It can be done in one loop

[@sourabhsisodia9563]

striver bhai tum bhot mast kam krta hain....

[@harshkumarsharma1169]

18:21 Is this just me who listened to some other noise here

[@hariomtiwari7605]

Superb Explanation Bhaiya 👌👌👌👌

[@rebellious_703]

Wah Arnab Wah ❤

[@Sneha-qz9ml]

The best explanation found!!..............

[@democratcobra]

Superb explanation ....

[@yashwagh83]

That T-shirt lol! But keep up with the good work, you explain shit very well!

[@ShubhamMahawar_Dancer_Actor]

The link you have provided for part2 is the link of Part 1 .reverify it.

[@sagarlandge3271]

crisp and clear!

[@studyaccount794]

Amazing explanation man!! Coded the brute-force myself after just watching the 1/3rd of the video. You're doing god's work!!

[@AKASHTHAKUR-rs4sg]

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

[@nileshsinha7869]

Great explanation..learned the concept of next smaller/greater 🔥

[@devbhattacharya153]

Best explanation video ever!!!

[@vm1662]

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; }

[@deepaksolanki1972]

Best Explanation, Hats off to the efforts. Subscribed !!!

[@sabbysays]

You are the best! Thanks for all the efforts :)

[@tusharjolly2734]

Best explanation!!!!

[@jitengarg5740]

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

[@takeUforward]

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

[@HarshGupta-wi1zn]

Getting runtime error segmentation fault error for the Same code in GFG. Expected time complexity : O(N) Expected Space complexity:O(N)

[@004-u6f]

same ,any idea how to correct it?

[@anupam6045]

Thanks striver for the wonderful explanation

[@cinime]

Amazing explanation, thank you very much!!

[@alamatel]

Thank you much for making this video.

[@akashskumar99]

superb explanation bruh

[@bahubaljain3063]

Just doing the same question.....and video aagyi 😂😂😂 ye mehaz itedaaq h ya khuda ka ishara🌸

[@dsa_tutorial]

we can also take 1 * 6 as 6 as height than also we will get rectangle whose area is maximum

[@h.kchannel4115]

Thank you for this great explanation!!!

[@gopropro3544]

Nicee T-Shirtt!!!!!

[@newbienate]

Rider doing good. Thanks

[@rydmerlin]

Why in the second example did you exclude the the first bar ? 1x5=5 why isn’t it 1x6?

[@dataman4503]

Can we do this in a single traversal? There are solutions in Leetcode Discuss with 1 traversal, but could not understand.

[@yashkhatwani3198]

Amazing

[@KRajesh-ej7dy]

Bro thanks for the video.I got total clarity after watching this.But the java code which u have given is not executing.

[@ananyaa8597]

Man this question is crazy

[@StudyEmail-p9u]

Thank You !!

[@suryansh70]

such a nice explaination

[@lBaZeRl]

Ain't no way nobody's talking about the fire shirt

[@ashishpradhan6250]

understood, thanks

[@ankitr2969]

great explanation!

[@123_shreyoshide9]

GOD LEVEL! THANK YOU!

[@kalebakeitshokile1366]

what a great explanation!

[@AnujSingh-ju4nr]

bhai itna stress mat diya karo, over ho jata hai kya ! heath ka dhyyan rakkho😄

[@aj9706]

Brilliant thanks

[@abhinay.k]

thank you

[@shubhamrane2918]

Thanks for the detailed explanation!!

[@shubhamrane2918]

Is there a playlist of the leetcode solutions on your channel?

[@haidarmohammad8510]

Why are you concern about greater element in the stack? Please reply..........

[@OrbitZyro]

because a bigger histogram / building / block is something ith element can expand into, but it cannot expand into a smaller one

[@dadidivya8663]

Python Sol: class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) li = [0 for i in range(n)] ri = [n-1 for i in range(n)] s1 = [0] s2 = [n-1] maxi = 0 for i in range(1,n): while(s1!=[] and heights[i]

[@satyampande684]

understood!!

[@aks-nc6kq]

Bro you look like munawar faruqui

[@chitranshkumar6694]

Thanks bhaiya for making this video

[@yahoo-kids]

oo bhaii maja aagya

[@souravsarkar6107]

understood sir

[@shwetanksingh5208]

//Brute force solution class Solution { public: int largestRectangleArea(vector& heights) { int ans = 0,n=heights.size(); for(int i=0;i=0 && heights[leftSmaller]>=heights[i]); ans = max(ans,(rightSmaller-leftSmaller-1)*heights[i]); } return ans; } };

[@zeeshanhasankhan]

ans = max(ans,(rightSmaller-leftSmaller+1)*heights[i]);

[@subashkannan949]

Indeed

[@jitendrasinghsola]

the link in the description is pointing to the same video not part 2

[@mihiragarwal1269]

loved the video

[@navyasri5077]

height of instagram..lol .actually this indicates i am listening so carefully 😋

[@anjaliyadav9360]

Thanks!

[@dreamyme543]

Understood

[@harshitjaiswal9439]

understood

[@jeevan999able]

Man thank you !

[@rubyshorts281]

actual video starts at 8:46

[@susantakumardutta6283]

Understood🙂🙂

[@COURATWENTYTHREE]

understood❤❤❤

[@vivekpawar311]

Understood!

[@surbhijain8800]

thank you very much!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! indeed helpful

[@abhisheksoni9644]

can we solve this using doubly linked list?

[@ayush.kumar.13907]

nice tshirt

[@khushil9988]

take a bow

[@rachanasingh2231]

awesome!!

[@gowthamarun43]

Super 💥💥

[@kyakya6490]

Liked it due to the tshirt lmao

[@srinathv1412]

Understood !!!!!

[@samdarshikumar6488]

🔥🔥🔥🔥🔥🔥 best

[@prashantbisht2219]

Shouldn't it be O(n^2), since consider an non increasing order array, for right side, we will delete every element greater than current, hence for every element we have to traverse till very first, shouldn't that be n^2 ???????????

[@takeUforward]

Every element is pushed once and popped out once. So ideally its 2n

[@prashantbisht2219]

@@takeUforward Yaaa I got it now, thanks dude, you even replied in your old videos, that's great..

[@khushil9988]

why i am feeling like this is similar to trapping rain water

[@aryanagarwal7903]

Concept is same