> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/stack/monotonic-stack/85.-maximal-rectangle.md).

# 85. Maximal Rectangle

## Problem Statement

<br>

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*.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg)

<pre><code><strong>Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
</strong><strong>Output: 6
</strong><strong>Explanation: The maximal rectangle is shown in the above picture.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: matrix = [["0"]]
</strong><strong>Output: 0
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: matrix = [["1"]]
</strong><strong>Output: 1
</strong></code></pre>

&#x20;

**Constraints:**

* `rows == matrix.length`
* `cols == matrix[i].length`
* `1 <= row, cols <= 200`
* `matrix[i][j]` is `'0'` or `'1'`.<br>

## Intuition

```
Basically, Just make a count of buildings from 
that point

Converting the problem to Largest rectangle in Histogram

For eg->

For above figure the values would be
1 0 1 0 0
2 0 2 1 1 so on

Basically on those row arrays, we apply histogram logic
```

### Links

<https://leetcode.com/problems/maximal-rectangle/description/>

### Video Links

<https://www.youtube.com/watch?v=tOylVCugy9k&ab_channel=takeUforward>

### Approach 1:

```
Monotonic Stack
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int rectangles_in_histogram(vector<int> &histo){
      stack < int > st;
      int maxA = 0;
      int n = histo.size();
      for (int i = 0; i <= n; i++) {
        while (!st.empty() && (i == n || histo[st.top()] >= histo[i])) {
          int height = histo[st.top()];
          st.pop();
          int width;
          if (st.empty())
            width = i;
          else
            width = i - st.top() - 1;
          maxA = max(maxA, width * height);
        }
        st.push(i);
      }
      return maxA;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> hist(m, vector<int>(n,0));

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int count = 0;

                for(int k=i; k>=0; k--){
                    if(matrix[k][j] == '1')
                        count++;

                    else 
                        break;
                }
                hist[i][j] = count;
            }
        }

        int maxi = 0;
        for(auto &it: hist){
            vector<int> temp(it);
            int ans = rectangles_in_histogram(it);

            maxi = max(maxi, ans);
        }
        
        return maxi;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###