Tutorialspoint.dev

Maximum size rectangle binary sub-matrix with all 1s

Given a binary matrix, find the maximum size rectangle binary-sub-matrix with all 1’s.
Example:

Input :   0 1 1 0
          1 1 1 1
          1 1 1 1
          1 1 0 0

Output :  1 1 1 1
          1 1 1 1

We have discussed a dynamic programming based solution for finding largest square with 1s.

In this post an interesting method is discussed that uses largest rectangle under histogram as a subroutine. Below are steps. 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.



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

Illustration :

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 8

Below is the implementation. It is strongly recommended to refer this post first as most of the code taken from there.

C++

// C++ program to find largest rectangle with all 1s
// in a binary matrix
#include<bits/stdc++.h>
using namespace std;
  
// Rows and columns in input matrix
#define R 4
#define C 4
  
// Finds the maximum area under the histogram represented
// by histogram.  See below article for details.
int maxHist(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<int> result;
  
    int top_val;     // Top of stack
  
    int max_area = 0; // Initialize max area in current
                      // row (or histogram)
  
    int area = 0;    // Initialize area with current top
  
    // 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.top()] <= 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.top()];
            result.pop();
            area = top_val * i;
  
            if (!result.empty())
                area = top_val * (i - result.top() - 1 );
            max_area = 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.top()];
        result.pop();
        area = top_val * i;
        if (!result.empty())
            area = top_val * (i - result.top() - 1 );
  
        max_area = max(area, max_area);
    }
    return max_area;
}
  
// Returns area of the largest rectangle with all 1s in A[][]
int maxRectangle(int A[][C])
{
    // Calculate area for first row and initialize it as
    // result
    int result = maxHist(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]) A[i][j] += A[i - 1][j];
  
  
        // Update result if area with current row (as last row)
        // of rectangle) is more
        result = max(result, maxHist(A[i]));
    }
  
    return result;
}
  
// Driver code
int main()
{
    int A[][C] = { {0, 1, 1, 0},
                   {1, 1, 1, 1},
                   {1, 1, 1, 1},
                   {1, 1, 0, 0},
                 };
  
    cout << "Area of maximum rectangle is "
         << maxRectangle(A);
  
    return 0;
}

Java

// Java program to find largest rectangle with all 1s
// in a binary matrix
import java.io.*;
import java.util.*;
   
class GFG 
{
    // Finds the maximum area under the histogram represented
    // by histogram.  See below article for details.
    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<Integer> result = new Stack<Integer>();
       
        int top_val;     // Top of stack
       
        int max_area = 0; // Initialize max area in current
                          // row (or histogram)
       
        int area = 0;    // Initialize area with current top
       
        // 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 maxRectangle(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;
    }
       
    // Driver code
    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 "
                                  maxRectangle(R,C,A));
    }
}
   
// Contributed by Prakriti Gupta

Python3

# Python3 program to find largest rectangle
# with all 1s in a binary matrix

# Rows and columns in input matrix
R = 4
C = 4



# Finds the maximum area under the histogram represented
# by histogram. See below article for details.
# https:#www.geeksforgeeks.org/largest-rectangle-under-histogram/
def maxHist(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.
result = []

top_val = 0 # Top of stack

max_area = 0 # Initialize max area in current
# row (or histogram)

area = 0 # Initialize area with current top

# Run through all bars of given
# histogram (or row)
i = 0
while (i < C): # If this bar is higher than the # bar on top stack, push it to stack if (len(result) == 0) or (row[result[0]] <= row[i]): result.append(i) i += 1 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[0]] result.pop(0) area = top_val * i if (len(result)): area = top_val * (i - result[0] - 1 ) max_area = max(area, max_area) # Now pop the remaining bars from stack # and calculate area with every popped # bar as the smallest bar while (len(result)): top_val = row[result[0]] result.pop(0) area = top_val * i if (len(result)): area = top_val * (i - result[0] - 1 ) max_area = max(area, max_area) return max_area # Returns area of the largest rectangle # with all 1s in A def maxRectangle(A): # Calculate area for first row and # initialize it as result result = maxHist(A[0]) # iterate over row to find maximum rectangular # area considering each row as histogram for i in range(1, R): for j in range(C): # if A[i][j] is 1 then add A[i -1][j] if (A[i][j]): A[i][j] += A[i - 1][j] # Update result if area with current # row (as last row) of rectangle) is more result = max(result, maxHist(A[i])) return result # Driver Code if __name__ == '__main__': A = [[0, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 0, 0]] print("Area of maximum rectangle is", maxRectangle(A)) # This code is contributed # by SHUBHAMSINGH10 [tabby title="C#"]

// C# program to find largest rectangle
// with all 1s in a binary matrix 
using System;
using System.Collections.Generic;
  
class GFG
{
// Finds the maximum area under the 
// histogram represented by histogram.
// See below article for details. 
public 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<int> result = new Stack<int>();
  
    int top_val; // Top of stack
  
    int max_area = 0; // Initialize max area in 
                      // current row (or histogram) 
  
    int area = 0; // Initialize area with 
                  // current top
  
    // 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.Count == 0 || 
            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.Count > 0)
            {
                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.Count > 0)
    {
        top_val = row[result.Peek()];
        result.Pop();
        area = top_val * i;
        if (result.Count > 0)
        {
            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[][] 
public static int maxRectangle(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;
}
  
// Driver code 
public static void Main(string[] args)
{
    int R = 4;
    int C = 4;
  
    int[][] A = new int[][]
    {
        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.Write("Area of maximum rectangle is "
                            maxRectangle(R, C, A));
}
}
  
// This code is contributed by Shrikant13


Output :

Area of maximum rectangle is 8


Time Complexity:
O(R x X)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter