Storing the width of consecutive 1’s ending at every cell (i, j) in a 2D array is the aim. Beginning from every cell (i, j) with value 1, iterate upwards row by row, determine the minimal width of 1’s in the column to guarantee the rectangle stays valid. The minimal width multiplied by the height yields the size of the rectangle, which updates the maximum area found thus far.
Initialize a 2D matrix memo of size nm to hold the width of successive 1s ending at every cell (i, j). Starting at 0 Go iteratively across every cell (i, j) in the input matrix. Should the value at (i, j) be 1, use these guidelines: Should j = 0, set memo[i][j] = 1; otherwise, set memo[i][j] = 1 + memo[i][j – 1]. Define width = memo[i][j]. Update width = min(width, memo[k][j] and get the rectangle area width(i – k + 1) for every row k from i to 0. Add to the maximum area discovered thus far.
Get back the computed maximum area.
C++
// C++ program to find the maximum area of
// rectangle in a 2D matrix.
#include <bits/stdc++.h>
using namespace std;
// 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();
// 2D matrix to store the width of 1's
// ending at each cell.
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;
// Set width of 1's at (i,j).
if (j == 0)
memo[i][j] = 1;
else
memo[i][j] = 1 + memo[i][j - 1];
int width = memo[i][j];
// Traverse row by row, update the
// 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
// Java program to find the maximum area of
// rectangle in a 2D matrix.
class GfG {
static int maxArea(int[][] mat) {
int n = mat.length, m = mat[0].length;
// 2D matrix to store the width of 1's
// ending at each cell.
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;
// Set width of 1's at (i,j).
if (j == 0) memo[i][j] = 1;
else memo[i][j] = 1 + memo[i][j - 1];
int width = memo[i][j];
// Traverse row by row, update the
// 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
# Python program to find the maximum area of
# rectangle in a 2D matrix.
def maxArea(mat):
n, m = len(mat), len(mat[0])
# 2D matrix to store the width of 1's
# ending at each cell.
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
# Set width of 1's at (i, j).
if j == 0:
memo[i][j] = 1
else:
memo[i][j] = 1 + memo[i][j - 1]
width = memo[i][j]
# Traverse row by row, update the
# 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#
// C# program to find the maximum area of
// rectangle in a 2D matrix.
using System;
class GfG {
static int maxArea(int[][] mat) {
int n = mat.Length, m = mat[0].Length;
// 2D matrix to store the width of 1's
// ending at each cell.
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;
// Set width of 1's at (i, j).
if (j == 0) memo[i, j] = 1;
else memo[i, j] = 1 + memo[i, j - 1];
int width = memo[i, j];
// Traverse row by row, update the
// 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(string[] args) {
int[][] mat = {
new int[]{0, 1, 1, 0},
new int[]{1, 1, 1, 1},
new int[]{1, 1, 1, 1},
new int[]{1, 1, 0, 0}
};
Console.WriteLine(maxArea(mat));
}
}JavaScript
// JavaScript program to find the maximum area of
// rectangle in a 2D matrix.
function maxArea(mat) {
let n = mat.length, m = mat[0].length;
// 2D matrix to store the width of 1's
// ending at each cell.
let 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;
// Set width of 1's at (i, j).
if (j === 0) memo[i][j] = 1;
else memo[i][j] = 1 + memo[i][j - 1];
let width = memo[i][j];
// Traverse row by row, update the
// minimum width and calculate area.
for (let k = i; k >= 0; k--) {
width = Math.min(width, memo[k][j]);
let area = width * (i - k + 1);
ans = Math.max(ans, area);
}
}
}
return ans;
}
let mat = [
[0, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 0, 0]
];
console.log(maxArea(mat));Output
8