Largest Empty Rectangle between Row Bounds
Autumn Tournament (2011)
Submission name: standard.cpp
Problem summary
Answer many queries asking for the largest all-zero rectangle entirely inside a given inclusive range of matrix rows.
Input
N M; N rows of M binary integers; Q; then Q pairs r1 r2 (1≤r1≤r2≤N).
Output
The maximum area for each row range.
Constraints
1≤N,M≤1000;1≤Q≤1000000.
Worked example
An independently prepared worked example; constructive outputs may have other valid forms.
Input
3 4 0 1 0 0 1 0 0 0 0 0 0 0 3 1 2 2 3 1 3
Output
4 6 6
Solution analysis
- For each bottom row b, form histogram heights: height[c] is the consecutive number of zeros ending at b. A monotonic stack finds, for every bar, the widest interval on which that bar is a minimum.
- Store the best width for each exact bar height, then propagate widths downward. width[h] becomes the longest run whose bars are all at least h, so h·width[h] is the largest zero rectangle ending at b with height h.
- Let answer[top][b] store the best rectangle inside the range. A rectangle either ends above b, excludes top, or spans the full height b−top+1. Take the maximum of answer[top][b−1], answer[top+1][b], and the corresponding histogram area. Process top downward. In the sample, rows2–3 contain a2×3 zero block of area6.
Why it works
Nearest-smaller histogram boundaries enumerate a maximum-width interval at every relevant height, and downward propagation handles heights absent as bar minima. The three DP cases cover every possible rectangle: if it uses both boundary rows it has the full range height; otherwise it belongs to a smaller interval. Induction on interval length proves all answers.
Watch out. The requested rectangle need not touch either queried boundary row. Include the two smaller-interval DP cases. Matrix values are space-separated, not necessarily row strings. Maximum area fits int.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<int>height(m),left(m),right(m),stack;
vector<vector<int>>answer(n+2,vector<int>(n+1));
for(int bottom=1;bottom<=n;bottom++){
for(int c=0;c<m;c++){
int value;
cin>>value;
height[c]=value==0?height[c]+1:0;
}
stack.clear();
for(int c=0;c<m;c++){
while(!stack.empty()&&height[stack.back()]>=height[c]){
stack.pop_back();
}
left[c]=stack.empty()?-1:stack.back();
stack.push_back(c);
}
stack.clear();
for(int c=m-1;c>=0;c--){
while(!stack.empty()&&height[stack.back()]>=height[c]){
stack.pop_back();
}
right[c]=stack.empty()?m:stack.back();
stack.push_back(c);
}
vector<int>width(bottom+2);
for(int c=0;c<m;c++){
width[height[c]]=max(width[height[c]],right[c]-left[c]-1);
}
for(int h=bottom-1;h>=1;h--){
width[h]=max(width[h],width[h+1]);
}
// Both proper row subintervals have already been computed.
for(int top=bottom;top>=1;top--){
int h=bottom-top+1;
answer[top][bottom]=max({answer[top][bottom-1],answer[top+1][bottom],h*width[h]});
}
}
int queries;
cin>>queries;
while(queries--){
int top,bottom;
cin>>top>>bottom;
cout<<answer[top][bottom]<<'\n';
}
}