Solution For Maximal Rectangle

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.

Step by Step Implementation For Maximal Rectangle

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int maxarea = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == '1'){
                    //compute the maximum width and update dp with it
                    dp[i][j] = j == 0 ? 1 : dp[i][j-1] + 1;
                    
                    int width = dp[i][j];
                    
                    //compute the maximum area rectangle with a lower right corner at [i, j]
                    for(int k = i; k >= 0; k--){
                        width = Math.min(width, dp[k][j]);
                        maxarea = Math.max(maxarea, width * (i - k + 1));
                    }
                }
            }
        }
        return maxarea;
    }
}

This problem can be solved using the stack data structure. We can keep track of the height of the rectangle at each index by using a stack. If the current height is greater than the height at the top of the stack, we push the current height onto the stack. If the current height is less than the height at the top of the stack, we keep popping from the stack until we find a height that is less than the current height. We can calculate the maximum rectangle area at each index by using the height and width (which is the current index minus the index of the first occurrence of the height in the stack).

def maximalRectangle(self, matrix):
        if not matrix:
            return 0
        n = len(matrix[0])
        height = [0] * (n + 1)
        stack = [-1]
        maxarea = 0
        for i in range(len(matrix)):
            for j in range(n):
                if matrix[i][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0
            j = 0
            while j < n + 1:
                if height[j] < height[stack[-1]]:
                    h = height[stack.pop()]
                    w = j - 1 - stack[-1]
                    maxarea = max(maxarea, h * w)
                else:
                    stack.append(j)
                    j += 1
        return maxarea

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:

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

The problem can be found here: https://leetcode.com/problems/maximal-rectangle/

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector left(n, 0), right(n, n), height(n, 0);
        int maxA = 0;
        for (int i = 0; i < m; i++) {
            int cur_left = 0, cur_right = n; 
            for (int j = 0; j < n; j++) { // compute height (can do this from either side)
                if (matrix[i][j] == '1') height[j]++; 
                else height[j] = 0;
            }
            for (int j = 0; j < n; j++) { // compute left (from left to right)
                if (matrix[i][j] == '1') left[j] = max(left[j], cur_left);
                else {left[j] = 0; cur_left = j + 1;}
            }
            // compute right (from right to left)
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') right[j] = min(right[j], cur_right);
                else {right[j] = n; cur_right = j;}    
            }
            // compute the area of rectangle (can do this from either side)
            for (int j = 0; j < n; j++)
                maxA = max(maxA, (right[j] - left[j]) * height[j]);
        }
        return maxA;
    }
};

using System; 

public class Solution {
    public int MaximalRectangle(char[,] matrix) {
        if (matrix == null || matrix.GetLength(0) == 0 || matrix.GetLength(1) == 0)
        {
            return 0;
        }
        
        int max = 0;
        int[,] dp = new int[matrix.GetLength(0),matrix.GetLength(1)];
        
        for (int i = 0; i < matrix.GetLength(0); i++)
        {
            for (int j = 0; j < matrix.GetLength(1); j++)
            {
                if (matrix[i,j] == '0')
                {
                    continue;
                }
                
                dp[i,j] = j == 0? 1 : dp[i,j-1] + 1;
                int width = dp[i,j];
                
                for (int k = i; k >= 0; k--)
                {
                    width = Math.Min(width, dp[k,j]);
                    int area = width * (i - k + 1);
                    max = Math.Max(max, area);
                }
            }
        }
        
        return max;
    }
}