# 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
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 ` `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. ` `// https://tutorialspoint.dev/slugresolver/largest-rectangle-under-histogram/ ` `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); ` ` `  `    ``// 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. ` `    ``// https://tutorialspoint.dev/slugresolver/largest-rectangle-under-histogram/ ` `    ``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;     ``// 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] <= 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] result.pop(0) area = top_val * i if (len(result)): area = top_val * (i - result - 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] result.pop(0) area = top_val * i if (len(result)): area = top_val * (i - result - 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) # 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.  ` `// https://tutorialspoint.dev/slugresolver/largest-rectangle-under-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); ` ` `  `    ``// 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)