Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Max Rectangle

Last Updated on March 29, 2022 by Ria Pathak

### Concepts Used:

DP/recursion and Stack.

Hard.

### Problem Statement :

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and print its area.

See original problem statement here

#### Test Case:

``````Input:
1
5 5
0 0 1 0 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 0 1 1 1

Output:
12

Explanation:
The inner matrix from index (1,1) to index (3,4) with area 12(3*4) gives the appropriate solution.``````

### Solving Approach:

The idea is to update each column of a given row with corresponding column of previous row and find largest histogram area for for that row.

`Steps:`

1. Find maximum area for row[0]
2. for each row in 1 to N – 1
``````for each column in that row
if A[row][column] == 1 then update A[row][column] with A[row][column] += A[row - 1][column]
find area for that row
and update maximum area so far``````

### Solutions:

```
#include
#include

// `M × N` matrix
#define M 4
#define N 5

// Utility function to replace all non-zero values in a matrix by 1
void resetMatrix(int mat[][N])
{
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (mat[i][j] != 0) {
mat[i][j] = 1;
}
}
}
}

// Utility function to find the maximum of two numbers
int max(int x, int y) {
return (x > y) ? x : y;
}

// Function to calculate the area of the largest rectangle of 1's where swapping of
// columns is allowed
int findMaxRectArea(int mat[][N])
{
// update the matrix to store the counts of consecutive 1's present in each column
for (int j = 0; j < N; j++)
{
// process each column from bottom to top
for (int i = M - 2; i >= 0; i--)
{
if (mat[i][j] == 1) {
mat[i][j] = mat[i+1][j] + 1;
}
}
}

// keep track of the largest rectangle of 1's found so far
int maxArea = 0;

// traverse each row in the modified matrix to find the maximum area
for (int i = 0; i < M; i++)
{
// create a count array for each row `i`
int count[M + 1] = { 0 };

// process row `i`
for (int j = 0; j < N; j++)
{
if (mat[i][j] > 0)
{
// increment value in the count array using the current element
// as an index
count[mat[i][j]] += 1;

// the area can be calculated by multiplying the current
// element `mat[i][j]` with the corresponding value
// in the count array `count[mat[i][j]]`

maxArea = max(maxArea, mat[i][j] * count[mat[i][j]]);
}
}
}

// reset matrix before returning
resetMatrix(mat);

return maxArea;
}

int main(void)
{
int mat[M][N] =
{
{0, 0, 1, 0, 1},
{0, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{0, 0, 1, 1, 1}
};

printf("The area of the largest rectangle of 1's is %d", findMaxRectArea(mat));

return 0;
}
```
``` #include
using namespace std;
bool sortby(const pair& a,
const pair& b)
{
if (a.first != b.first)
return a.first < b.first;
return (a.second < b.second);
}
bool kOverlap(vector > pairs, int k)
{
vector > vec;
for (int i = 0; i < pairs.size(); i++) {

vec.push_back(make_pair( pairs[i].first, -1 ));
vec.push_back(make_pair( pairs[i].second, +1 ));
}
sort(vec.begin(), vec.end());
stack > st;
for (int i = 0; i < vec.size(); i++) {
pair cur = vec[i];
if (cur.second == -1) {
st.push(cur);
}
else {
st.pop();
}
if (st.size() >= k) {
return true;
}
}
return false;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
vector > pairs;
int x,y;
for(int i=0;i>x>>y;
pairs.push_back(make_pair(x,y));
}
if(kOverlap(pairs,k))
cout<<"Yes"<

```
```import java.util.*;

class maxRectangle
{
static int maxHist(int R, int C, int row[])
{
/* Create an empty stack. The stack holds indexes of
hist[] array/ The bars stored in stack are always
in increasing order of their heights. */
Stack result = new Stack();

int top_val;

int max_area = 0;

int area = 0;

// Run through all bars of given histogram (or row)
int i = 0;
while (i < C)
{
// If this bar is higher than the bar on top
// stack, push it to stack
if (result.empty()
|| row[result.peek()] <= row[i])
result.push(i++);
else {
/* If this bar is lower than top of stack,
then calculate area of rectangle with
stack top as the smallest (or minimum
height) bar. 'i' is 'right index' for the
top and element before top in stack is
'left index' */
top_val = row[result.peek()];
result.pop();
area = top_val * i;

if (!result.empty())
area
= top_val * (i - result.peek() - 1);
max_area = Math.max(area, max_area);
}
}
/* Now pop the remaining bars from stack and
calculate area with every popped bar as the smallest bar */
while (!result.empty())
{
top_val = row[result.peek()];
result.pop();
area = top_val * i;
if (!result.empty())
area = top_val * (i - result.peek() - 1);

max_area = Math.max(area, max_area);
}
return max_area;
}
// Returns area of the largest rectangle with all 1s in A[][]
static int max(int R, int C, int A[][])
{
// Calculate area for first row and initialize it as result
int result = maxHist(R, C, A[0]);
/* iterate over row to find maximum rectangular area
considering each row as histogram */
for (int i = 1; i < R; i++)
{
for (int j = 0; j < C; j++)

// if A[i][j] is 1 then add A[i -1][j]
if (A[i][j] == 1)
A[i][j] += A[i - 1][j];
// Update result if area with current row (as
// last row of rectangle) is more
result = Math.max(result, maxHist(R, C, A[i]));
}
return result;
}
public static void main(String[] args)
{
int R = 4;
int C = 4;

int A[][] = {
{ 0, 1, 1, 0 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 0, 0 },
};
System.out.print("Area of maximum rectangle is "+ max(R, C, A));
}
}

```
```def sortby(a, b):

if (a[0] != b[0]):
return a[0] < b[0]

return (a[1] < b[1])

def kOverlap(pairs, k):

vec = []
for i in range(len(pairs)):

vec.append([ pairs[i][0], -1 ])
vec.append([ pairs[i][1], +1 ])

vec.sort()
st = []
for i in range(len(vec)):

cur = vec[i]

if (cur[1] == -1):
st.append(cur)

else:
st.pop()

if (len(st) >= k):
return True

return False

for _ in range(int(input())):

n, k =map(int,input().split())
pairs = []
for i in range(n):
pairs.append(list(map(int,input().split())))

if kOverlap(pairs, k):
print("Yes")
else:
print("No")
```

[forminator_quiz id="1967"]

This article tried to discuss the concept of Recursion, Stack. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming