PROBLEM LINK
Breaking the Fence
Author:-Faiz Alam
Editorialist:-Faiz Alam
Tester:-Prasoon Jain
PREREQUISITES
Stack,Largest Area of the Histogram
PROBLEM
There exists a wooden fence made up of wooden planks each of them of varying heights
but having width equals to 1 meter.A rabbit named harry wants to cross the wooden fence .In order to help him you have to cut a maximum possible rectangular or a square area of the wooden fence.Find that area .
EXPLANATION
This problem is a simple implementation of finding largest rectangular area of a histogram problem.In order to find the largest possible area of the fence you have to find that plank having next smaller height to the left and to the right for each of the planks,that will give the range of planks that can be included for forming area.Then you have to maximize the area by taking each planks.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> calleft(vector<int>&a,int n)
{
vector <int> v;
stack < pair<int,int> > st;
for(int i=0;i<n;i++)
{
if(st.empty())
v.push_back(-1);
else if(!st.empty()&&st.top().first<a[i])
{
v.push_back(st.top().second);
}
else
{
while(!st.empty()&&st.top().first>=a[i])
{
st.pop();
}
if(st.empty())
v.push_back(-1);
else
v.push_back(st.top().second);
}
st.push({a[i],i});
}
return v;
}
vector<int> calright(vector<int>&a,int n)
{
vector <int> v;
stack < pair<int,int> > st;
for(int i=n-1;i>=0;i--)
{
if(st.empty())
v.push_back(n);
else if(!st.empty()&&st.top().first<a[i])
{
v.push_back(st.top().second);
}
else
{
while(!st.empty()&&st.top().first>=a[i])
{
st.pop();
}
if(st.empty())
v.push_back(n);
else
v.push_back(st.top().second);
}
st.push({a[i],i});
}
reverse(v.begin(),v.end());
return v;
}
int largestArea(vector<int>& heights) {
int size=heights.size();
vector<int>l; //find Next smaller to left for each plank and store in vector
vector<int>r; //find Next smaller to right for each plank and store in vector
vector<int>res;
l=calleft(heights,size);
r=calright(heights,size);
for(int i=0;i<size;i++)res.push_back(heights[i]*abs(r[i]-l[i]-1)); //for each plank find the range of length that
// will form the rectangle
return *max_element(res.begin(),res.end()); //returning the max possible area of them
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n; // n correspond to number of wooden plank
vector<int>heights(n); //height corresponds to height of each wooden plank
for(int i=0;i<n;i++)
{
cin>>heights[i];
}
cout<<largestArea(heights)<<"\n";
}
return 0;
}
Complexity:-O(N)