Given a binary matrix, find the maximum size rectangle binary-sub-matrix with all 1’s.
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
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.
# 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.
# 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#"]
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