Maximum Area Rectangle of 1s in a Binary Matrix

Last Updated : 15 Sep, 2025

Given a 2D binary matrix mat[][] consisting only of 0s and 1s, find the area of the largest rectangle sub-matrix that contains only 1s.

Examples: 

Input: mat[][] = [[0, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 0, 0]]
Output: 8
Explanation: The largest rectangle with only 1's is from (1, 0) to (2, 3) which is

409843080


Input: mat[][] = [[0, 1, 1],
[1, 1, 1],
[0, 1, 1]]
Output: 6
Explanation: The largest rectangle with only 1's is from (0, 1) to (2, 2) which is

409843081
Try it on GfG Practice
redirect icon

Table of Content

[Approach 1] Using Largest Rectangular Area in a Histogram - O(n*m) Time and O(m) Space

Instead of directly searching the whole matrix, think row by row. For every row, treat it as the base of a rectangle and see how far rectangles of 1’s can extend upward.

Build Heights Array

  • Maintain an array height[] where height[j] stores the count of consecutive 1’s in column j up to the current row.
  • If you encounter a 0, reset that column’s height to 0.

Now, after updating height[] for a row, the problem becomes identical to finding the largest rectangle area in a histogram formed by height[].

The idea is to treat each row as the ground and encode vertical runs of 1’s into a histogram (height[]). Then the known stack-based largest-rectangle-in-histogram gives the max area for that base repeat for all rows and take the max.

C++ 
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// Function to find the maximum area of 
// rectangle in a histogram.
int getMaxArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> s;
    int res = 0;
    
    for (int i = 0; i < n; i++) {
      
        // Process all bars that are higher or equal to current
        while (!s.empty() && heights[s.top()] >= heights[i]) {
            int tp = s.top(); 
            s.pop();

            // Width between previous smaller (stack top) and current index
            int width = s.empty() ? i : i - s.top() - 1;
            
            res = max(res, heights[tp] * width);
        }
        s.push(i);
    }

    // Process remaining bars in stack
    while (!s.empty()) {
        int tp = s.top(); 
        s.pop();

        int width = s.empty() ? n : n - s.top() - 1;
        res = max(res, heights[tp] * width);
    }

    return res;
}

// Function to find the maximum area of rectangle
// in a 2D matrix.
int maxArea(vector<vector<int>> &mat) {
    int n = mat.size(), m = mat[0].size();
    
    // heights will store histogram heights
    vector<int> heights(m, 0);
    int ans = 0;
   
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
       
            // Update histogram heights
            if (mat[i][j] == 1) heights[j]++;
            else heights[j] = 0;
        }
        ans = max(ans, getMaxArea(heights));
    }
    
    return ans;
}

int main() {
    vector<vector<int>> mat = {
        {0,1,1,0},
        {1,1,1,1},
        {1,1,1,1},
        {1,1,0,0}
    };
         
    cout << maxArea(mat) << endl;  
    
    return 0;
}
Java 
import java.util.Stack;

public class GFG {

    // Function to find the maximum area of 
    // rectangle in a histogram.
    static int getMaxArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> s = new Stack<>();
        int res = 0;

        for (int i = 0; i < n; i++) {
            
            // Process all bars that are higher or equal to current
            while (!s.isEmpty() && heights[s.peek()] >= heights[i]) {
                int tp = s.pop();

            
                // Width between previous smaller (stack top) and current index
                int width = s.isEmpty() ? i : i - s.peek() - 1;

                res = Math.max(res, heights[tp] * width);
            }
            s.push(i);
        }

        // Process remaining bars in stack
        while (!s.isEmpty()) {
            int tp = s.pop();
            int width = s.isEmpty() ? n : n - s.peek() - 1;
            res = Math.max(res, heights[tp] * width);
        }

        return res;
    }

    // Function to find the maximum area of rectangle
    // in a 2D matrix.
    static int maxArea(int[][] mat) {
        int n = mat.length, m = mat[0].length;

        // heights will store histogram heights
        int[] heights = new int[m];
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
        
                // Update histogram heights
                if (mat[i][j] == 1) heights[j]++;
                else heights[j] = 0;
            }
            ans = Math.max(ans, getMaxArea(heights));
        }

        return ans;
    }

    public static void main(String[] args) {
        int[][] mat = {
            {0,1,1,0},
            {1,1,1,1},
            {1,1,1,1},
            {1,1,0,0}
        };

        System.out.println(maxArea(mat)); 
    }
}
Python 
# Function to find the maximum area of 
# rectangle in a histogram.
def getMaxArea(heights):
    n = len(heights)
    s = []
    res = 0

    for i in range(n):
    
        # Process all bars that are higher or equal to current
        while s and heights[s[-1]] >= heights[i]:
            tp = s.pop()

            # Width between previous smaller (stack top) and current index
            width = i if not s else i - s[-1] - 1

            res = max(res, heights[tp] * width)
        s.append(i)

    # Process remaining bars in stack
    while s:
        tp = s.pop()
        width = n if not s else n - s[-1] - 1
        res = max(res, heights[tp] * width)

    return res


# Function to find the maximum area of rectangle
# in a 2D matrix.
def maxArea(mat):
    n, m = len(mat), len(mat[0])

    # heights will store histogram heights
    heights = [0] * m
    ans = 0

    for i in range(n):
        for j in range(m):
    
            # Update histogram heights
            if mat[i][j] == 1:
                heights[j] += 1
            else:
                heights[j] = 0
        ans = max(ans, getMaxArea(heights))

    return ans


if __name__ == "__main__":
    mat = [
        [0,1,1,0],
        [1,1,1,1],
        [1,1,1,1],
        [1,1,0,0]
    ]
    print(maxArea(mat))
C# 
using System;
using System.Collections.Generic;

class GFG {

    // Function to find the maximum area of 
    // rectangle in a histogram.
    static int getMaxArea(int[] heights) {
        int n = heights.Length;
        Stack<int> s = new Stack<int>();
        int res = 0;

        for (int i = 0; i < n; i++) {
        
            // Process all bars that are higher or equal to current
            while (s.Count > 0 && heights[s.Peek()] >= heights[i]) {
                int tp = s.Pop();

                // Width between previous smaller (stack top) and current index
                int width = (s.Count == 0) ? i : i - s.Peek() - 1;

                res = Math.Max(res, heights[tp] * width);
            }
            s.Push(i);
        }

        // Process remaining bars in stack
        while (s.Count > 0) {
            int tp = s.Pop();
            int width = (s.Count == 0) ? n : n - s.Peek() - 1;
            res = Math.Max(res, heights[tp] * width);
        }

        return res;
    }

    // Function to find the maximum area of rectangle
    // in a 2D matrix.
    static int maxArea(int[,] mat) {
        int n = mat.GetLength(0), m = mat.GetLength(1);

        // heights will store histogram heights
        int[] heights = new int[m];
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
        
                // Update histogram heights
                if (mat[i, j] == 1) heights[j]++;
                else heights[j] = 0;
            }
            ans = Math.Max(ans, getMaxArea(heights));
        }

        return ans;
    }

    static void Main() {
        int[,] mat = {
            {0,1,1,0},
            {1,1,1,1},
            {1,1,1,1},
            {1,1,0,0}
        };

        Console.WriteLine(maxArea(mat));  
    }
}
JavaScript 
// Function to find the maximum area of 
// rectangle in a histogram.
function getMaxArea(heights) {
    let n = heights.length;
    let s = [];
    let res = 0;

    for (let i = 0; i < n; i++) {
        
        // Process all bars that are higher or equal to current
        while (s.length > 0 && heights[s[s.length - 1]] >= heights[i]) {
            let tp = s.pop();

        
            // Width between previous smaller (stack top) and current index
            let width = (s.length === 0) ? i : i - s[s.length - 1] - 1;

            res = Math.max(res, heights[tp] * width);
        }
        s.push(i);
    }

    // Process remaining bars in stack
    while (s.length > 0) {
        let tp = s.pop();
        let width = (s.length === 0) ? n : n - s[s.length - 1] - 1;
        res = Math.max(res, heights[tp] * width);
    }

    return res;
}

// Function to find the maximum area of rectangle
// in a 2D matrix.
function maxArea(mat) {
    let n = mat.length, m = mat[0].length;

    // heights will store histogram heights
    let heights = new Array(m).fill(0);
    let ans = 0;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
        
            // Update histogram heights
            if (mat[i][j] === 1) heights[j]++;
            else heights[j] = 0;
        }
        ans = Math.max(ans, getMaxArea(heights));
    }

    return ans;
}

// Driver Code
let mat = [
    [0,1,1,0],
    [1,1,1,1],
    [1,1,1,1],
    [1,1,0,0]
];

console.log(maxArea(mat));

Output
8

[Approach 2] Using Dynamic Programming - O((n^2)*m) Time and O(n*m) Space

The idea is to store, for each cell (i, j), the width of consecutive 1’s ending at that position in a 2D array. Then, for every cell (i, j) with value 1, iterate upwards row by row. While moving upward, keep track of the minimum width of 1’s seen so far in that column. This ensures the rectangle formed remains valid. At each step, the rectangle area is computed as: (area = minWidth * height)

C++ 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxArea(vector<vector<int>> &mat) {
    int n = mat.size(), m = mat[0].size();

    // memo[i][j] stores the width of consecutive 1's
    // ending at position (i, j).
    vector<vector<int>> memo(n, vector<int>(m, 0));
    int ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 0) continue;

            // Compute width of 1's at (i, j).
            memo[i][j] = (j == 0) ? 1 : memo[i][j - 1] + 1;

            int width = memo[i][j];

            // Traverse upwards row by row,
            // update minimum width and calculate area.
            for (int k = i; k >= 0; k--) {
                width = min(width, memo[k][j]);
                int area = width * (i - k + 1);
                ans = max(ans, area);
            }
        }
    }

    return ans;
}

int main() {
    vector<vector<int>> mat = {
        {0, 1, 1, 0},
        {1, 1, 1, 1},
        {1, 1, 1, 1},
        {1, 1, 0, 0}
    };

    cout << maxArea(mat) << endl; 

    return 0;
}
Java 
public class GFG {
    static int maxArea(int[][] mat) {
        int n = mat.length, m = mat[0].length;

        // memo[i][j] stores the width of consecutive 1's
        // ending at position (i, j).
        int[][] memo = new int[n][m];
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) continue;

                // Compute width of 1's at (i, j).
                memo[i][j] = (j == 0) ? 1 : memo[i][j - 1] + 1;

                int width = memo[i][j];

                // Traverse upwards row by row,
                // update minimum width and calculate area.
                for (int k = i; k >= 0; k--) {
                    width = Math.min(width, memo[k][j]);
                    int area = width * (i - k + 1);
                    ans = Math.max(ans, area);
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int[][] mat = {
            {0, 1, 1, 0},
            {1, 1, 1, 1},
            {1, 1, 1, 1},
            {1, 1, 0, 0}
        };

        System.out.println(maxArea(mat)); 
    }
}
Python 
def maxArea(mat):
    n, m = len(mat), len(mat[0])

    # memo[i][j] stores the width of consecutive 1's
    # ending at position (i, j).
    memo = [[0] * m for _ in range(n)]
    ans = 0

    for i in range(n):
        for j in range(m):
            if mat[i][j] == 0:
                continue

            # Compute width of 1's at (i, j).
            memo[i][j] = 1 if j == 0 else memo[i][j - 1] + 1

            width = memo[i][j]

            # Traverse upwards row by row,
            # update minimum width and calculate area.
            for k in range(i, -1, -1):
                width = min(width, memo[k][j])
                area = width * (i - k + 1)
                ans = max(ans, area)

    return ans


if __name__=="__main__":
    mat = [
        [0, 1, 1, 0],
        [1, 1, 1, 1],
        [1, 1, 1, 1],
        [1, 1, 0, 0]
    ]
    
    print(maxArea(mat))
C# 
using System;

class GFG {
    static int maxArea(int[,] mat) {
        int n = mat.GetLength(0), m = mat.GetLength(1);

        // memo[i][j] stores the width of consecutive 1's
        // ending at position (i, j).
        int[,] memo = new int[n, m];
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i, j] == 0) continue;

                // Compute width of 1's at (i, j).
                memo[i, j] = (j == 0) ? 1 : memo[i, j - 1] + 1;

                int width = memo[i, j];

                // Traverse upwards row by row,
                // update minimum width and calculate area.
                for (int k = i; k >= 0; k--) {
                    width = Math.Min(width, memo[k, j]);
                    int area = width * (i - k + 1);
                    ans = Math.Max(ans, area);
                }
            }
        }

        return ans;
    }

    static void Main() {
        int[,] mat = {
            {0, 1, 1, 0},
            {1, 1, 1, 1},
            {1, 1, 1, 1},
            {1, 1, 0, 0}
        };

        Console.WriteLine(maxArea(mat)); 
    }
}
JavaScript 
function maxArea(mat) {
    const n = mat.length, m = mat[0].length;

    // memo[i][j] stores the width of consecutive 1's
    // ending at position (i, j).
    const memo = Array.from({ length: n }, () => Array(m).fill(0));
    let ans = 0;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (mat[i][j] === 0) continue;

            // Compute width of 1's at (i, j).
            memo[i][j] = (j === 0) ? 1 : memo[i][j - 1] + 1;

            let width = memo[i][j];

            // Traverse upwards row by row,
            // update minimum width and calculate area.
            for (let k = i; k >= 0; k--) {
                width = Math.min(width, memo[k][j]);
                const area = width * (i - k + 1);
                ans = Math.max(ans, area);
            }
        }
    }

    return ans;
}

// Driver Code
const mat = [
    [0, 1, 1, 0],
    [1, 1, 1, 1],
    [1, 1, 1, 1],
    [1, 1, 0, 0]
];

console.log(maxArea(mat));

Output
8

Related articles:

Comment

Explore