Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area. For example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Thoughts

The most basic solution involves calculating the area of the largest rectangle for each element in the matrix which is 1. We can implement this by iterating through the matrix in a top-down + left-right fashion, and checking for the largest rectangle that forms to its right and down sides.

To check for the largest rectangle, we can find the maximum length of each row of 1s to the right & below the current element. This might form either a rectangle, or an uneven surface.

maximal rectangle area

To calculate the area of the rectangle is easy, but to calculate the maximum area in an uneven surface is the problem of calculating the largest area in a histogram. This problem takes O(n) time, where n is the number of bars in the histogram. Counting the length of the bars is necessary too, which makes the total time to calculate an uneven surface’s area in our problem O(n * m).

This would make the brute force solution have a time complexity of O(n2 * m2) and a space complexity of O(min(n, m)) [because of largest area in a histogram].

Efficient solution

Once we figure out that we can effectively find the area of an uneven surface using the histogram algorithm, we realize that instead of iterating through the entire array, we can go row by row, calculating the current histogram at each level. This greatly optimizes the time needed to calculate the maximum area.

The way we implement it is to cumulatively add rows with consecutive ones as we go down the rows. The value is reset to 0 if a particular row value is 0. This gives us a histogram with the current row as the base and the lengths calculated so that we can find the current largest area. We keep track of the largest area found yet, and at the end of the iteration, we have the largest rectangle in the matrix.

Show me the implementation

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        maxArea = 0
        hist = [int(i) for i in matrix[0]]
     
        # Create a copy of the first row
        # self.findLargestArea(histogram) is the helper 
        # function that calculates the area of the current histogram

        maxArea = max(maxArea, self.findLargestArea(hist))

        for i in range(1, len(matrix)):
            # Add the previous row to the next row if it is one
            hist = [hist[j] + int(matrix[i][j]) 
                 if int(matrix[i][j]) > 0 else 0 for j in range(len(matrix[i]))]

            maxArea = max(maxArea, self.findLargestArea(hist))

        return maxArea
        
    def findLargestArea(self, inp: List[int]):
        if len(inp) < 2:
            return inp[0] if len(inp) == 1 else 0
        stack = []
        maxArea = 0
        for i in range(len(inp)):
            if len(stack) == 0 or inp[stack[-1]] <= inp[i]:
                stack.append(i)
            else:
                while len(stack) > 0 and inp[stack[-1]] > inp[i]:
                    current = stack.pop()
                    maxArea = max(maxArea, 
                       (i - 1 - stack[-1] if len(stack) > 0 else i) * inp[current])
                stack.append(i)

        if len(stack) > 0:
            i = len(inp)
            while len(stack) > 0:
                current = stack.pop()
                 maxArea = max(maxArea, 
                     (i - 1 - stack[-1] if len(stack) > 0 else i) * inp[current])

        return maxArea

The time complexity of this code is O(n * m) and the space complexity is O(n).

Questions: Can you do it in-place? Can you reduce the space usage in the code above?