Finding the biggest size rectangle binary-sub-matrix with all 1’s from a 2d binary matrix mat[][] is the goal.
Example
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
[1, 1, 1, 1]
[1, 1, 1, 1]
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
[1, 1]
[1, 1]
[1, 1]Table of Content
- Using Largest Rectangular Area in a Histogram Approach – O(n*m) Time and O(m) Space
- Using Dynamic Programming (Memoization) – O((n^2)*m) Time and O(n*m) Space
Time and O(m) Space Using Largest Rectangular Area in a Histogram Approach
This method derives from the Largest Rectangular Area in a Histogram concept.
The concept is to discover the largest size rectangle in the matrix by first treating every row as the basis of a histogram.
The greatest area of the histogram can be obtained knowing the height of the bars. This allows one to discover the histogram’s largest area of bars in each row. Update the next row with the previous row and determine the greatest area under the histogram, so using each 1’s as filled squares and 0’s with an empty square and considering each row as the basis.
Illustration:
Input :
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
Step 1:
0 1 1 0 maximum area = 2
Step 2:
row 1 1 2 2 1 area = 4, maximum area becomes 4
row 2 2 3 3 2 area = 8, maximum area becomes 8
row 3 3 4 0 0 area = 6, maximum area remains 8C++
// 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 histogram.
int getMaxArea(vector<int>& arr) {
int n = arr.size();
stack<int> s;
int res = 0;
int tp, curr;
for (int i = 0; i < n; i++) {
while (!s.empty() && arr[s.top()] >= arr[i]) {
// The popped item is to be considered as the
// smallest element of the histogram
tp = s.top();
s.pop();
// For the popped item previous smaller element is
// just below it in the stack (or current stack top)
// and next smaller element is i
int width = s.empty() ? i : i - s.top() - 1;
res = max(res, arr[tp] * width);
}
s.push(i);
}
// For the remaining items in the stack, next smaller does
// not exist. Previous smaller is the item just below in
// stack.
while (!s.empty()) {
tp = s.top(); s.pop();
curr = arr[tp] * (s.empty() ? n : n - s.top() - 1);
res = max(res, curr);
}
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();
// Array to store matrix
// as a histogram.
vector<int> arr(m, 0);
int ans = 0;
// Traverse row by row.
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (mat[i][j]==1) {
arr[j]++;
}
else {
arr[j] = 0;
}
}
ans = max(ans, getMaxArea(arr));
}
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.
import java.util.Stack;
class GfG {
// Function to find the maximum area of
// rectangle in a histogram.
static int getMaxArea(int[] arr) {
int n = arr.length;
Stack<Integer> s = new Stack<>();
int res = 0;
int tp, curr;
for (int i = 0; i < n; i++) {
while (!s.isEmpty() && arr[s.peek()] >= arr[i]) {
// The popped item is to be considered as the
// smallest element of the histogram
tp = s.pop();
// For the popped item previous smaller element is
// just below it in the stack (or current stack top)
// and next smaller element is i
int width = s.isEmpty() ? i : i - s.peek() - 1;
res = Math.max(res, arr[tp] * width);
}
s.push(i);
}
// For the remaining items in the stack, next smaller does
// not exist. Previous smaller is the item just below in
// stack.
while (!s.isEmpty()) {
tp = s.pop();
curr = arr[tp] * (s.isEmpty() ? n : n - s.peek() - 1);
res = Math.max(res, curr);
}
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;
// Array to store matrix
// as a histogram.
int[] arr = new int[m];
int ans = 0;
// Traverse row by row.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 1) {
arr[j]++;
} else {
arr[j] = 0;
}
}
ans = Math.max(ans, getMaxArea(arr));
}
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.
# Function to find the maximum area of
# rectangle in a histogram.
def getMaxArea(arr):
n = len(arr)
s = []
res = 0
for i in range(n):
while s and arr[s[-1]] >= arr[i]:
# The popped item is to be considered as the
# smallest element of the histogram
tp = s.pop()
# For the popped item previous smaller element is
# just below it in the stack (or current stack top)
# and next smaller element is i
width = i if not s else i - s[-1] - 1
res = max(res, arr[tp] * width)
s.append(i)
# For the remaining items in the stack, next smaller does
# not exist. Previous smaller is the item just below in
# stack.
while s:
tp = s.pop()
curr = arr[tp] * (n if not s else n - s[-1] - 1)
res = max(res, curr)
return res
# Function to find the maximum area of rectangle
# in a 2D matrix.
def maxArea(mat):
n = len(mat)
m = len(mat[0])
# Array to store matrix
# as a histogram.
arr = [0] * m
ans = 0
# Traverse row by row.
for i in range(n):
for j in range(m):
if mat[i][j] == 1:
arr[j] += 1
else:
arr[j] = 0
ans = max(ans, getMaxArea(arr))
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;
using System.Collections.Generic;
class GfG {
// Function to find the maximum area of
// rectangle in a histogram.
static int getMaxArea(int[] arr) {
int n = arr.Length;
Stack<int> s = new Stack<int>();
int res = 0, tp, curr;
for (int i = 0; i < n; i++) {
while (s.Count > 0 && arr[s.Peek()] >= arr[i]) {
// The popped item is to be considered as the
// smallest element of the histogram
tp = s.Pop();
// For the popped item previous smaller element is
// just below it in the stack (or current stack top)
// and next smaller element is i
int width = s.Count == 0 ? i : i - s.Peek() - 1;
res = Math.Max(res, arr[tp] * width);
}
s.Push(i);
}
// For the remaining items in the stack, next smaller does
// not exist. Previous smaller is the item just below in
// stack.
while (s.Count > 0) {
tp = s.Pop();
curr = arr[tp] * (s.Count == 0 ? n : n - s.Peek() - 1);
res = Math.Max(res, curr);
}
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;
// Array to store matrix
// as a histogram.
int[] arr = new int[m];
int ans = 0;
// Traverse row by row.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 1) {
arr[j]++;
} else {
arr[j] = 0;
}
}
ans = Math.Max(ans, getMaxArea(arr));
}
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 to find the maximum area of
// rectangle in a histogram.
function getMaxArea(arr) {
let n = arr.length;
let s = [];
let res = 0;
for (let i = 0; i < n; i++) {
while (s.length > 0 && arr[s[s.length - 1]] >= arr[i]) {
// The popped item is to be considered as the
// smallest element of the histogram
let tp = s.pop();
// For the popped item previous smaller element is
// just below it in the stack (or current stack top)
// and next smaller element is i
let width = s.length === 0 ? i : i - s[s.length - 1] - 1;
res = Math.max(res, arr[tp] * width);
}
s.push(i);
}
// For the remaining items in the stack, next smaller does
// not exist. Previous smaller is the item just below in
// stack.
while (s.length > 0) {
let tp = s.pop();
let curr = arr[tp] * (s.length === 0 ? n : n - s[s.length - 1] - 1);
res = Math.max(res, curr);
}
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;
// Array to store matrix
// as a histogram.
let arr = new Array(m).fill(0);
let ans = 0;
// Traverse row by row.
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (mat[i][j] === 1) {
arr[j]++;
} else {
arr[j] = 0;
}
}
ans = Math.max(ans, getMaxArea(arr));
}
return ans;
}
const mat = [
[0, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 0, 0]
];
console.log(maxArea(mat));Output
8