Leetcode 85 - Maximal Rectangle

Problem Description

Leetcode 85 - Maximal Rectangle

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Thought Process / Intuition

When I first saw this problem, I wanted to give up. I have only solved 1 hard problem before this, and it was a DFS question. I tried tackling this problem, thinking it was a dynamic programming problem, but was stuck and gave up. I decided to go and read my friend Kurt's solution, which I will link here.

Kurt's Writeup

This problem is a variation of the "Largest Rectangle in Histogram" problem. The idea is to build up the histogram row by row and calculate the largest rectangle that can be formed under the histogram at each row. By doing this for each row, we can find the largest rectangle that can be formed in the entire matrix.

Here's how it works:

1. Each row is treated as a base, forming the heights array to represent the heights of 'bars' of 1s above each column. When moving to the next row, heights are updated accordingly: increasing by 1 for encountering a 1, or resetting to 0 for a 0.

2. With the updated heights array for each row, the largest rectangle that can be formed in the histogram represented by the heights is determined.

3. Use stacks to efficiently track the expansion limits of each 'bar' in the histogram, scanning the heights array from left to right and right to left. The expansion limits for each 'bar' in the histogram are identified by tracking the indices of the previous smaller bar on the left and the next smaller bar on the right.

4. For each height, considering its expansion limits, the largest rectangle that includes that height as the highest bar is calculated. The maximum area encountered is retained as the answer.

Through these steps, potential rectangle areas are built up and tracked row by row, ultimately yielding the largest rectangle possible in the entire matrix.

Approach

The solution tackles the problem through two key functions: maximalRectangle and largestRectangleArea.

maximalRectangle Function:

• Scans each row of the matrix and updates the heights array to represent the height of the rectangle ending at each index.
• It iterates through each row, updating heights based on encountering 1s or 0s.
• Calls largestRectangleArea to compute the largest rectangle in the histogram described by heights.
• Tracks the maximum area encountered after processing each row.

largestRectangleArea Function:

• Computes the largest rectangle area in a histogram represented by heights.
• Initializes left and right arrays to store indices of next smaller elements to the left and right, respectively, for each bar.
• Utilizes a stack to determine bounds for each bar, facilitating area calculation.
• Returns the maximum area found.olves checking for left leaves and making recursive calls to traverse the tree.

Solution

class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
    heights = [0 for _ in range(len(matrix[0]))]
    largest_area = 0
    for row in matrix:
        for idx, value in enumerate(row):
            if value == "1":
                heights[idx] += 1
            else:
                heights[idx] = 0
        largest_area = max(largest_area, self.largestRectangleArea(heights))
    return largest_area
def largestRectangleArea(self, heights: List[int]) -> int:
    num_heights = len(heights)
    stack = []
    prev_smaller = [-1 for _ in range(num_heights)]
    next_smaller = [num_heights for _ in range(num_heights)]
    for i, height in enumerate(heights):
        while stack and heights[stack[-1]] >= height:
            stack.pop()
        if stack:
            prev_smaller[i] = stack[-1]
        stack.append(i)
    stack = []
    for j in range(num_heights - 1, -1, -1):
        curr_height = heights[j]
        while stack and heights[stack[-1]] >= curr_height:
            stack.pop()
        if stack:
            next_smaller[j] = stack[-1]
        stack.append(j)
    largest_area = max(
        height * (next_smaller[i] - prev_smaller[i] - 1) for i, height in enumerate(heights)
    )
    return largest_area

Walkthrough

Complexity Analysis

Time complexity: $O(n^2)$

• For every row,
• We are creating the histograms: $O(n)$
• We perform largest rectangle in histogram: $O(n)$

Space complexity: $O(n^2)$

• The largestRectangleArea function utilizes additional space for arrays (heights, left, right, and stk), each of size n, leading to a total space complexity of $O(n)$, where n is the number of columns.
• Therefore, the total space complexity is $O(n)$.