Largest Rectangle in Histogram 🔥 | Stack Data structure & Algorithms Hello World Leetcode #84

This is the video under the series of DATA STRUCTURE & ALGORITHM in a STACK Playlist. Now we are going to solve a stack problem Largest Rectangle in Histogram Leetcode or Largest Rectangular Area in a Histogram

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

► 84. Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where the width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = of 10 units.

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

*Follow me *

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

►Our Playlists on:-

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

🌟 Please leave a LIKE ❤️ and SUBSCRIBE for more AMAZING content! 🌟

✨ Tags ✨
leetcode problems
leetcode problems java
leetcode problems python
leetcode problems that got me tired
leetcode problems c++
leetcode problems and solutions python
leetcode problems playlist
leetcode problems and solutions java
leetcode problems in Hindi
leetcode problems javascript
leetcode problems and solutions
leetcode problems of the day
leetcode problems for beginners
leetcode problems easy
leetcode problems js
stack practice problems
stack practice problems gfg
leetcode stack questions
leetcode stack queue
stack hello world
Largest Rectangle in Histogram leetcode solution
Largest Rectangle in Histogram gfg
Largest Rectangle in Histogram
question asked in Google
off-campus placement
Online Stock Span
Practice stack data structure
Stack in a data structure in Hindi
Stack Full playlist for Beginners
algorithms
graph DSA
data structure
sorting algorithms
time-complexity analysis
gate computer science preparation
programming languages

#stack #Leetcode #programming

[Shadow-lxrh]

Sir just now fnshd viewing all ur stack videos thank you soo much
1. For providing que in description and code link in leetcode and gfg(helps to practice ques multiple times and understand the twist)
2. For pdf as well as code(it is very helpful when i watch in 240p coz my internet amount is less)
3. More than anything thank you from the core of my heart really really really
for starting the video by saying that ques is very easy and
insisting that we first try to solve it and stopping in middle of vdeo and telling us to try the further part
This implies for ur tree and grap playlist also as a newbie to CP i was intimidated on seeing all the complex content in yt and problems in website.
But after knowing abt this channel in yt recommendation i feel that this was really a boon to me.
All ur playlist Start frm scratch utterly which is very helpful

My only request to u is that pls if possible try to make some different playlists too like dynamic prgming and other topics which u feel impo to be Known.

When u teach i feel as if u teach straight frm ur heart genuinely pls continue this good work means a lot 🙏

[bhavyanegi]

WOW BHAIIYA VERY VERY ESAY AND EFFECTIVE WAY OF EXPLANATION YOU PUT OUT TOO MUCH EFFORT TO MAKE THIS THANKYOU BHAII

[viveksoni]

Apke video dekhne ke baad doubt ho aisa nhi hua abbhi tak.
Thank you for those valuable videos and do cover more leetcode solutions which are importan. Thank you

[harshitasingh]

Greatt workk..Your explanation is soo good

[smilemania]

Nice aise pdhaya karo har question sir naive to optimise. Best 👍😂👍

[SomneelMaity]

Thanks Bhaiya, this video was really helpful, I solved the question in O(N) when you said "Do It Yourself".

[amanavengeraman]

Gotcha greate Explaintion.

Try to upload daily atleast 1 video if possible

[rajankhunt]

This video quality is soo good. please consistency maintain this.

[VickeyKumar-fw]

maja hi aagaya es question par, time laga but aacha question tha

[priyanshuthakur]

class Solution {
public int largestRectangleArea(int[] heights) {
int n=heights.length;
Stack<Integer>st=new Stack<Integer>();
int[] ps=new int[n];
int[] ns=new int[n];
for(int i=0;i<n;i++){

st.pop();
}
if(st.isEmpty()){
ps[i]=-1;
}else{
ps[i]=st.peek();
}
st.push(i);
}
while(!st.isEmpty()){
st.pop();
}
for(int i=n-1;i>=0;i--){

st.pop();
}
if(st.isEmpty()){
ns[i]=n;
}else{
ns[i]=st.peek();
}
st.push(i);
}
int max=0;
for(int i=0;i<n;i++){
int
max=Math.max(max, cur);
}
return max;
}
}

[sugammehta]

How can we find for a largest square in a histogram? What changes can we make?

[dipanshuraj]

bhaiya I have a doubt about how to find the time complexity of this code could you explain it?

[subhankarkunar]

Hi, Subhankar. I have 6 years of experience in TCS. Is it possible to move to product based company. Will they consider my profile

[darshantrivedi]

Bhaiya please make a video on your resume please 🙏

[Maheshwaripremierleague]

int get_max_area(vector<int> a)
{
stack<int> st;
int n = a.size(), ans=0, i=0;
a.push_back(0);
while(i<n)
{
while (!st.empty() and a[st.top()]>a[i])
{
int h = a[st.top()];
st.pop();
if(st.empty())
{
ans = max(ans, h*i);
}
else
{
int len = i-st.top()-1;
ans = max(ans, h*len);
}

}
st.push(i);
i++;
}
return ans;
}

[showsshorts]

sir i think in naive approach curr+=arr[i] ki jagah cur+=cur;

[parthanuj]

why this problem feels like container with most water on gfg .

[only_for_funr]

i have written the same code and its working also but after submitting its showing TLE when all values are same please help


my code



class Solution {
public:
vector<int> right_min(vector<int>& h)
{
vector<int> ans2;
stack<int> st;
int n=h.size();
for(int i=n-1;i>=0;i--)
{
while(!st.empty() && h[st.top()]>=h[i])
st.pop();
int res=(st.empty()) ? n:st.top();
ans2.push_back(res);
st.push(i);
}
reverse(ans2.begin(), ans2.end());
return ans2;
}
vector<int> left_min(vector<int>& h)
{
vector<int> ans1;
stack<int> st;
int n=h.size();
for(int i=0;i<h.size();i++)
{
while(!st.empty() && h[st.top()]>=h[i])
st.pop();
int res=st.empty() ? -1:st.top();
ans1.push_back(res);
st.push(i);
}
return ans1;
}
int h) {
int maxi=-1;
vector<int> ans1=left_min(h);
vector<int> ans2=right_min(h);
for(int i=0;i<h.size();i++)
{

int

maxi=max(maxi, area);
}
return maxi;
}
};

[deepanshjohri]

My Approach :


class Solution {
public:
int heights) {

/* BRUTE FORCE : O(N*N) using array data structure only and for loop


int n=heights.size();
vector<int> pre(n, -1), post(n, -1);



//finding pre
for(int i=n-1;i>=0;i--)
{
bool check=false;
for(int j=i-1;j>=0;j--)
{
if(heights[i]>heights[j])
{
pre[i]=j;
check=true;
break;
}
}
if(check==true)
check=false;
}


//finding post
for(int i=0;i<n;i++)
{
bool check=false;
for(int j=i+1;j<n;j++)
{
if(heights[i]>heights[j])
{
post[i]=j;
check=true;
break;
}
}
if(check==false)
post[i]=n;
else
check=false;
}

//finding maximum difference of post and pre and return the answer
int answer=INT_MIN;
for(int i=0;i<n;i++)
{
int diff=0;
if(pre[i]==-1)
diff=post[i];
else
diff=post[i]-pre[i]-1;
diff=diff*heights[i];
answer=max(answer, diff);
}

cout<<"pre below\n";
for(auto it:pre)
cout<<it<<" ";
cout<<"\npost below\n";
for(auto it:post)
cout<<it<<" ";
cout<<"\n";

return answer;

OPTIMIZED APPROACH : Using Stack
*/



//finding next smaller element using Stack concept

int n=heights.size();
stack<pair<int, int>> stack, stacks;
vector<int> next(n, n);
stack.push({heights[n-1], n-1});
stacks.push({heights[0], 0});
for(int i=n-2;i>=0;i--)
{
int element=heights[i];
while(!stack.empty() and element<=stack.top().first)
stack.pop();
if(!stack.empty())
next[i]=stack.top().second;
stack.push({element, i});
}

//finding previous smaller element using Stack concept
vector<int> prev(n, -1);
for(int i=1;i<n;i++)
{
int element=heights[i];
while(!stacks.empty() and element<=stacks.top().first)
stacks.pop();
if(!stacks.empty())
prev[i]=stacks.top().second;
stacks.push({element, i});
}

//finding maximum difference of post and pre and return the answer
int answer=INT_MIN;
for(int i=0;i<n;i++)
{
int diff=0;
if(prev[i]==-1)
diff=next[i];
else
diff=next[i]-prev[i]-1;
diff=diff*heights[i];
answer=max(answer, diff);
}
return answer;


}
};