Largest Rectangle in Histogram | Part - 1 | Leetcode 84

Watch at 1.25x for better experience ..

---------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------
✅Use coupon-code "STRIVER" for getting 10% on all subscriptions of Unacademy

---------------------------------------------------------------------------------------------------------------------------
Products that I use:

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

##dsa​ #striver #leetcode

[manojnavinjamuri]

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.

[divyagupta]

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

[nihalsingh]

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

[stutisuchak]

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

[anshuljain]

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

[ankitsablok]

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.

[mukeshmahajan]

bhai the energy with which u explain incredibly amazing!

[localhost_]

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

[akshyagarg]

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

[mayi-hg]

9:27 enjoy.
btw great video as usual.

[DeepakKumar-ychr]

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

[sandeshkumarchandrakar]

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

[nonamenoname-xj]

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

[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

[yashwagh]

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

[nehasingh]

Great job! You explain every concept so

[AKASHTHAKUR-rssg]

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

[yashkumardhawan]

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

[sunnykumarpal]

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

[studyaccount]

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