Problem Statement in English

You are given an m x n binary matrix matrix filled with '0's and '1's. Find the largest rectangle containing only '1's and return its area.

Approach

This is a little tricky to come up with.

We can think of each row as the base of a histogram, where the height of each column is the number of consecutive 1s up to and including that row.

If the latest row has a 0, the height for that column resets to 0.

Now that we have the heights for each column, up to and including the current row, we can use the “Largest Rectangle in Histogram” approach to find the maximum area for that row.

As we iterate through the heights for each column, we maintain a stack that helps us keep track of the indices and heights of the bars in the histogram.

When we encounter a height that is less than the height of the bar at the top of the stack, we pop from the stack and calculate the area of the rectangle that can be formed with the popped height as the smallest (or minimum height) bar.

This is because the older bar cannot extend beyond the current index, and we can calculate the area using the width from the index of the popped bar to the current index, and discard the popped bar.

At the end of the iteration for the heights, we process any remaining bars in the stack to ensure we consider all possible rectangles.

Solution in Python


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        ROWS = len(matrix)
        COLS = len(matrix[0])

        heights = [0] * COLS
        ans = 0

        for i in range(ROWS):
            for j in range(COLS):
                matrix[i][j] = int(matrix[i][j])

        def largestRectangleInHistogram():
            nonlocal ans

            stack = []

            for i, h in enumerate(heights):
                effective_index = i

                while stack and stack[-1][1] > h:
                    index, oldH = stack.pop()
                    ans = max(ans, (i - index) * oldH)

                    effective_index = index

                stack.append((effective_index, h))

            for i, h in stack:
                ans = max(ans, (COLS - i) * h)

        for i in range(ROWS):
            for j in range(COLS):
                # compounded row
                if not matrix[i][j]:
                    heights[j] = 0
                elif matrix[i][j]:
                    heights[j] += 1

            largestRectangleInHistogram()
        
        return ans

Complexity

  • Time: $O(m \times n)$
    Where m is the number of rows and n is the number of columns in the matrix. For each row, we compute the heights and then run the largest rectangle in histogram algorithm which takes $O(n)$ time.

  • Space: $O(n)$
    Since we are using an additional array heights of size n to store the heights of the histogram for each column.

Mistakes I Made

I had to look this up :(

And we are done.