> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/maximal-rectangle.md).

# 85. Maximal Rectangle

### Description

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

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/maximal-rectangle/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-maximal-rectangle-java/)
* [YouTube](https://youtu.be/g8bSdXCG-lA)

### **Examples**

{% tabs %}
{% tab title="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
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(row*column)
 * Space complexity : O(column)
 */

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || 
           matrix.length == 0 || 
           matrix[0].length == 0) return 0;
        
        int m = matrix.length, n = matrix[0].length;
        int[] heights = new int[n];
        
        int maxRect = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int value = matrix[i][j]-'0';
                heights[j] = (value == 0)? 0: (value + heights[j]);
            }
            maxRect = Math.max(maxRect, largestRectangleArea(heights));
        }
        return maxRect;
    }
    
    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, area = 0;
        
        while(i < heights.length) {
            if(stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.add(i++);
            } else {
                area = Math.max(area, calculateArea(stack, heights, i));
            }
        }
        
        while(!stack.isEmpty()) {
            area = Math.max(area, calculateArea(stack, heights, i));
        }
        
        return area;
    }

    private int calculateArea(Stack<Integer> stack, int[] heights, int i) {
        int height = heights[stack.pop()];
        int weight = (stack.isEmpty())? i: (i-stack.peek()-1);
        return height * weight;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*