Maximum Area in Binary Matrix in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int maxHist(int a[],int n){
    int st[100],t=-1,mx=0;
    for(int i=0;i<=n;i++){
        int h=(i==n)?0:a[i];
        while(t!=-1 && h<a[st[t]]){
            int ht=a[st[t--]];
            int w=(t==-1)?i:i-st[t]-1;
            if(ht*w>mx) mx=ht*w;
        }
        st[++t]=i;
    }
    return mx;
}
int main(){
    int M[4][4]={{0,1,1,0},{1,1,1,1},{1,1,1,1},{1,1,0,0}},r=4,c=4,mx=0,h[4]={0};
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++) h[j]=(M[i][j]==0)?0:h[j]+1;
        int area=maxHist(h,c);
        if(area>mx) mx=area;
    }
    printf("%d",mx);
}

C Output

8

C++ Program

#include <bits/stdc++.h>
using namespace std;
int maxHist(vector<int>& a){
    stack<int> st; int n=a.size(),mx=0;
    for(int i=0;i<=n;i++){
        int h=(i==n)?0:a[i];
        while(!st.empty() && h<a[st.top()]){
            int ht=a[st.top()]; st.pop();
            int w=st.empty()?i:i-st.top()-1;
            mx=max(mx,ht*w);
        }
        st.push(i);
    }
    return mx;
}
int main(){
    vector<vector<int>> M={{0,1,1,0},{1,1,1,1},{1,1,1,1},{1,1,0,0}};
    int r=M.size(),c=M[0].size(),mx=0; vector<int> h(c,0);
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++) h[j]=M[i][j]?h[j]+1:0;
        mx=max(mx,maxHist(h));
    }
    cout<<mx;
}

C++ Output

8

JAVA Program

import java.util.*;
class Main{
    static int maxHist(int[] a){
        Stack<Integer> st=new Stack<>(); int mx=0,n=a.length;
        for(int i=0;i<=n;i++){
            int h=(i==n)?0:a[i];
            while(!st.isEmpty() && h<a[st.peek()]){
                int ht=a[st.pop()];
                int w=st.isEmpty()?i:i-st.peek()-1;
                mx=Math.max(mx,ht*w);
            }
            st.push(i);
        }
        return mx;
    }
    public static void main(String[] args){
        int[][] M={{0,1,1,0},{1,1,1,1},{1,1,1,1},{1,1,0,0}};
        int r=M.length,c=M[0].length,mx=0; int[] h=new int[c];
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++) h[j]=M[i][j]==0?0:h[j]+1;
            mx=Math.max(mx,maxHist(h));
        }
        System.out.println(mx);
    }
}

JAVA Output

8

Python Program

def maxHist(a):
    st=[];mx=0
    for i in range(len(a)+1):
        h=0 if i==len(a) else a[i]
        while st and h<a[st[-1]]:
            ht=a[st.pop()]
            w=i if not st else i-st[-1]-1
            mx=max(mx,ht*w)
        st.append(i)
    return mx

M=[[0,1,1,0],[1,1,1,1],[1,1,1,1],[1,1,0,0]]
r,c=len(M),len(M[0]);h=[0]*c;mx=0
for i in range(r):
    for j in range(c):
        h[j]=0 if M[i][j]==0 else h[j]+1
    mx=max(mx,maxHist(h))
print(mx)

Python Output

8

Detailed Explanation

Example

Consider the binary matrix:

0 1 1 0

1 1 1 1

1 1 1 1

1 1 0 0

The maximum rectangle of 1s is a 2×4 slab in the center (rows 2 and 3, columns 2–5), with area 8.

Real-Life Analogy

Consider this matrix as a floor plan where 1 denotes "free space" and 0 denotes "obstacle."

You wish to put the biggest rectangular rug that fits inside free space only.

You begin in the first row and continue to pile free spaces on top of each other vertically. Each row informs you of how tall each column's "stack of free blocks" is.

This makes each row a histogram, and the largest rectangle problem from earlier comes into play perfectly.

Step-By-Step Logic

This is a variant of Largest Rectangle in Histogram.

We iterate the matrix row by row.

For every row:

If the cell is 1, increment its height by 1 from the height of the previous row.

If it's 0, set height to 0 (since an obstacle disconnects things).

After we have this height array, we apply the histogram algorithm to obtain the maximum area for that row's heights.

We maintain the maximum over all rows.

For instance:

Row 1 heights: [0,1,1,0] → Largest rectangle = 2

Row 2 heights: [1,2,2,1] → Largest rectangle = 6

Row 3 heights: [2,3,3,2] → Largest rectangle = 8 (winner)

Row 4 heights: [3,4,0,0] → Largest rectangle = 6

Why It Matters

It's not just a theoretical exercise — it's the basis of the maximal rectangle problem in computer vision.

If you’ve ever used a photo editor that auto-selects the largest rectangular region without breaks, this algorithm is running in the background.

It’s also key in document scanning apps to detect tables or rectangular shapes from a binary map of pixels.

Learning Insights

It teaches how a complex 2D problem can be reduced to a simpler, reusable 1D problem.

Rather than creating a fresh rectangle-finding algorithm for 2D, you apply the histogram technique recursively to transformed rows.

A strong design pattern: break down a difficult problem to many easier subproblems and solve them individually.

Real-World Applications

Optical Character Recognition (OCR): finding the biggest text block in scanned documents.

Urban Planning: determining the biggest empty land rectangle in a zoning map.

Game Development: finding the biggest safe zone in a 2D game map.

Data Visualization: identifying the biggest contiguous area of high values within a binary heatmap.

Interview Tips

Interviewers prefer this because it tests:

Your capability to relate a familiar issue (histogram) to a different one (binary matrix).

Whether you are thinking in terms of state carryover from row to row.

Whether you can deal with O(rows × columns) complexity without additional space.

SEO-Friendly Closing

Maximum rectangle in binary matrix is a very common coding interview problem which extends directly from largest rectangle in histogram algorithm. By transforming every row into a histogram of heights and using a stack-based O(n) algorithm, you can solve to find the maximum rectangle of 1s efficiently in O(rows × columns) time. This technique is common in image processing, map interpretation, and matrix optimization problems, so it is an essential skill to know for interviews and practical applications.