Maximal Rectangle - Leetcode Solution

Problem Statement:

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

Example 1:

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

Solution:

The brute force solution is to consider every possible rectangle. For each cell, calculate the maximum rectangle that can be formed starting from that cell. This requires O(n^4) time complexity.

A better approach is to use dynamic programming. We can create a matrix dp[i][j] where dp[i][j] represents the maximum number of consecutive 1s ending at position (i, j). To calculate dp[i][j], we can look at three positions: dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. If matrix[i][j] is 1, we can set dp[i][j] as the minimum of these three positions plus 1. Otherwise, dp[i][j] is 0.

For each row, we can calculate the maximum rectangle by treating the previous row as a histogram. We can use the maximum rectangle area in a histogram algorithm to solve this problem. The time complexity of this approach is O(n^2).

Let's look at an example:

Input:

[ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]

Matrix dp:

[ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,2,2], [1,0,0,1,0] ]

For the first row, the histogram is [1,0,1,0,0]. The maximum rectangle is of height 1 and width 1, which has an area of 1.

For the second row, the histogram is [2,0,2,1,1]. The maximum rectangle is of height 2 and width 3, which has an area of 6.

For the third row, the histogram is [3,1,3,2,2]. The maximum rectangle is of height 3 and width 2, which has an area of 6.

For the fourth row, the histogram is [4,0,0,3,0]. The maximum rectangle is of height 3 and width 1, which has an area of 3.

Therefore, the answer for this input is 6.

Here's the Python code that implements this solution:

def maximalRectangle(matrix: List[List[str]]) -> int: if not matrix: return 0

m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]

for i in range(m):
    for j in range(n):
        if matrix[i][j] == '1':
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

area = 0
for i in range(m):
    heights = [0] * n
    for j in range(n):
        if matrix[i][j] == '1':
            heights[j] = dp[i][j]
    area = max(area, maxAreaInHistogram(heights))
return area

def maxAreaInHistogram(heights: List[int]) -> int: if not heights: return 0

n = len(heights)
left = [0] * n
right = [n] * n
stack = []

for i in range(n):
    while stack and heights[stack[-1]] >= heights[i]:
        right[stack[-1]] = i
        stack.pop()
    left[i] = stack[-1] if stack else -1
    stack.append(i)

area = 0
for i in range(n):
    area = max(area, heights[i] * (right[i] - left[i] - 1))
return area

The time complexity of this solution is O(m*n), where m and n are the dimensions of the matrix.

1