Max Rectangle

Concepts Used:

DP/recursion and Stack.

Difficulty Level:

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

Leave a Reply

Your email address will not be published. Required fields are marked *