Problem Explanation

We are given a 2D binary matrix filled with 0's and 1's. The goal of this problem is to find and return the area of the largest rectangle formed by '1's.

For instance, let's consider an example:

1
2
3Input: 
4[
5  ["1","0","1","0","0"],
6  ["1","0","1","1","1"],
7  ["1","1","1","1","1"],
8  ["1","0","0","1","0"]
9]
10
11Output: 6

In the above 2D matrix, if we look at 2nd column onward, there exists a rectangle of size 2x3 (2 rows and 3 columns) which only contains '1's. Hence the area of rectangle is 2*3 = 6.

Solution Approach

The problem can be solved using dynamic programming and utilizing a variation of the largest rectangle in histogram problem. Each row in the matrix is treated as the histogram and we find the largest rectangle in the histogram for each row.

Here is how the solution works step by step:

• Initialize an array 'hist' of size equal to number of columns in the matrix.

• For each row in the matrix, update the 'hist' array where 'hist[i]' denotes the height of the histogram at 'i'th column. If matrix[row][i] is '0' then height is 0, else height is previous height + 1.

• After height of histogram is calculated for each row, we calculate maximum area of rectangle for each histogram using a stack based approach. Here's how it works, for each element in hist:

  • While stack is not empty and height at current index is smaller than height at stack top, then keep removing bar from stack and calculate area. The current index keeps extending the width of rectangle in stack.
  • If height at current index is larger, then push it to stack.

Python Solution

1
2python
3class Solution:
4    def maximalRectangle(self, matrix):
5        if not matrix:
6            return 0
7
8        max_area = 0
9        heights = [0] * (len(matrix[0]) + 1)
10        
11        for row in matrix:
12            for i in range(len(row)):
13                heights[i] = heights[i] + 1 if row[i] == '1' else 0
14            
15            stack = [-1]
16            for i in range(len(heights)):
17                while heights[i] < heights[stack[-1]]:
18                    h = heights[stack.pop()]
19                    w = i - 1 - stack[-1]
20                    max_area = max(max_area, h * w)
21                stack.append(i)
22                
23        return max_area

In the python solution, the Solution class has a method maximalRectangle which calculates the maximum area rectangle. The heights list maintains the height of histograms. The main loop scans each row of the matrix and updates heights. The inner loop calculates the maximum area for current histogram using a stack.

Java Solution

1
2java
3public class Solution {
4    public int maximalRectangle(char[][] matrix) {
5        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
6        int[] height = new int[matrix[0].length];
7        for(int i = 0; i < matrix[0].length; i ++){
8            if(matrix[0][i] == '1') height[i] = 1;
9        }
10        int result = largestInLine(height);
11        for(int i = 1; i < matrix.length; i ++){
12            resetHeight(matrix, height, i);
13            result = Math.max(result, largestInLine(height));
14        }
15        return result;
16    }
17    
18    private void resetHeight(char[][] matrix, int[] height, int idx){
19        for(int i = 0; i < matrix[0].length; i ++){
20            if(matrix[idx][i] == '1') height[i] += 1;
21            else height[i] = 0;
22        }
23    }    
24    
25    private int largestInLine(int[] height){
26        if(height == null || height.length == 0) return 0;
27        int length = height.length;
28        Stack<Integer> s = new Stack<Integer>();
29        int max = 0;
30        for(int i = 0; i <= length; i ++){
31            int h = (i == length ? 0 : height[i]);
32            if(s.isEmpty() || h >= height[s.peek()]){
33                s.push(i);
34            }else{
35                int tp = s.pop();
36                max = Math.max(max, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
37                i--;
38            }
39        }
40        return max;
41    }
42}

In the Java solution, we have three helper methods maximalRectangle, resetHeight and largestInLine. Similar to Python, maximalRectangle initializes the height of histograms and calculates maximum area. The resetHeight method is used to update height for each row in the matrix. largestInLine calculates the largest rectangle for current histogram.

Note

The solution for other like JavaScript, C++, C# will have a similar approach. Unfortunately, I don't have enough expertise in these languages to provide solutions.

JavaScript Solution

Here's the JavaScript solution using the same dynamic programming approach:

1
2javascript
3var maximalRectangle = function(matrix) {
4    if (!matrix.length) return 0;
5    let heights = Array(matrix[0].length).fill(0);
6    let maxArea = 0;
7    for (let row of matrix) {
8        for (let i=0; i<row.length; i++) {
9            heights[i] = row[i] === '0' ? 0 : heights[i] + 1;
10        }
11        maxArea = Math.max(maxArea, largestRectangleArea(heights));
12    }
13    return maxArea;
14};
15
16
17var largestRectangleArea = function(heights) {
18    let maxArea = 0;
19    let stack = [-1];
20    for (let i=0; i<heights.length; i++) {
21        while (stack.length > 1 && heights[i] < heights[stack[stack.length-1]]) {
22            maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack[stack.length-1] - 1));
23        }
24        stack.push(i);
25    }
26    while (stack.length > 1) {
27        maxArea = Math.max(maxArea, heights[stack.pop()] * (heights.length - stack[stack.length-1] - 1));
28    }
29    return maxArea;
30};

The maximalRectangle function initializes a heights array to keep track of the heights of the histogram at each column and updates this array for each row in the matrix. The largestRectangleArea helper function, which computes the area of the largest rectangle in the histogram, is called for each row, and the maximum area is updated accordingly.

Note that the overall structure of the code matches the Python and Java solutions, but JavaScript has unique syntax for array handling. This code takes advantage of JavaScript's built-in Array and Math functions, as well as 'let' for block scope variable declarations.