Maximum size rectangle binary sub-matrix with all 1s

Last Updated : 18 Mar, 2024

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 :
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:
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

There is already an algorithm discussed a dynamic programming based solution for finding the largest square with 1s.

Approach:

In this post, an interesting method is discussed that uses largest rectangle under histogram as a subroutine.

If the height of bars of the histogram is given then the largest area of the histogram can be found. This way in each row, the largest area of bars of the histogram can be found. To get the largest rectangle full of 1’s, update the next row with the previous row and find the largest area under the histogram, i.e. consider each 1’s as filled squares and 0’s with an empty square and consider each row as the base.

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 8

Algorithm:

Run a loop to traverse through the rows.

Now If the current row is not the first row then update the row as follows, if matrix[i][j] is not zero then matrix[i][j] = matrix[i-1][j] + matrix[i][j].

Find the maximum rectangular area under the histogram, consider the ith row as heights of bars of a histogram. This can be calculated as given in this article Largest Rectangular Area in a Histogram

Do the previous two steps for all rows and print the maximum area of all the rows.

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

Implementation

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 
  
    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 
  
# Finds the maximum area under the 
# histogram represented 
# by histogram. See below article for details. 
  
  
class Solution(): 
    def maxHist(self, 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 of stack 
        top_val = 0
  
        # Initialize max area in current 
        max_area = 0
        # row (or histogram) 
  
        area = 0  # Initialize area with current top 
  
        # Run through all bars of given 
        # histogram (or row) 
        i = 0
        while (i < len(row)): 
  
            # If this bar is higher than the 
            # bar on top stack, push it to stack 
            if (len(result) == 0) or (row[result[-1]] <= 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.pop()] 
                area = top_val * i 
  
                if (len(result)): 
                    area = top_val * (i - result[-1] - 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.pop()] 
            area = top_val * i 
            if (len(result)): 
                area = top_val * (i - result[-1] - 1) 
  
            max_area = max(area, max_area) 
  
        return max_area 
  
    # Returns area of the largest rectangle 
    # with all 1s in A 
    def maxRectangle(self, A): 
  
        # Calculate area for first row and 
        # initialize it as result 
        result = self.maxHist(A[0]) 
  
        # iterate over row to find maximum rectangular 
        # area considering each row as histogram 
        for i in range(1, len(A)): 
  
            for j in range(len(A[i])): 
  
                # 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, self.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]] 
    ans = Solution() 
  
    print("Area of maximum rectangle is", 
          ans.maxRectangle(A)) 
  
# This code is contributed 
# by Aaryaman Sharma 

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. 
    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

Javascript

<script> 
    // Javascript program to find largest rectangle 
    // with all 1s in a binary matrix 
      
    // Finds the maximum area under the 
    // histogram represented by histogram. 
    function maxHist(R, C, 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. 
        let result = []; 
   
        let top_val; // Top of stack 
   
        let max_area = 0; // Initialize max area in 
        // current row (or histogram) 
   
        let area = 0; // Initialize area with 
        // current top 
   
        // Run through all bars of 
        // given histogram (or row) 
        let i = 0; 
        while (i < C) { 
            // If this bar is higher than the 
            // bar on top stack, push it to stack 
            if (result.length == 0 
                || row[result[result.length - 1]] <= 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[result.length - 1]]; 
                result.pop(); 
                area = top_val * i; 
   
                if (result.length > 0) { 
                    area = top_val * (i - result[result.length - 1] - 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.length > 0) { 
            top_val = row[result[result.length - 1]]; 
            result.pop(); 
            area = top_val * i; 
            if (result.length > 0) { 
                area = top_val * (i - result[result.length - 1] - 1); 
            } 
   
            max_area = Math.max(area, max_area); 
        } 
        return max_area; 
    } 
   
    // Returns area of the largest 
    // rectangle with all 1s in A[][] 
    function maxRectangle(R, C, A) 
    { 
        // Calculate area for first row 
        // and initialize it as result 
        let result = maxHist(R, C, A[0]); 
   
        // iterate over row to find 
        // maximum rectangular area 
        // considering each row as histogram 
        for (let i = 1; i < R; i++) { 
            for (let 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; 
    } 
      
    let R = 4; 
    let C = 4; 
  
      let A = [ [ 0, 1, 1, 0 ], 
               [ 1, 1, 1, 1 ], 
               [ 1, 1, 1, 1 ], 
               [ 1, 1, 0, 0 ] ]; 
    document.write("Area of maximum rectangle is "
                  + maxRectangle(R, C, A)); 
      
    // This code is contributed by decode2207. 
</script>

Output

Area of maximum rectangle is 8

Complexity Analysis:

Time Complexity: O(R x C x C).
One traversal of the matrix is required, another is traversal of every column, so the time complexity is O(R X C X C)
Auxiliary Space: O(C).
Stack is required to store the columns, so space complexity is O(C)

Suggest improvement

Matrix Chain Multiplication | DP-8

Construct Ancestor Matrix from a Given Binary Tree

Share your thoughts in the comments

Basic Operations on Matrix

Easy problems on Matrix

Intermediate problems on Matrix

Hard problems on Matrix