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.

Example 1:

```Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
```

Example 2:

```Input: matrix = []
Output: 0
```

Example 3:

```Input: matrix = [["0"]]
Output: 0
```

Example 4:

```Input: matrix = [["1"]]
Output: 1
```

Example 5:

```Input: matrix = [["0","0"]]
Output: 0
```

Constraints:

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

Idea:

Dynamic Programing

• Time complexity: O(mn)
• Space complexity: O(mn)
``````dp[i][j] := max length of all 1s ends with col j at row i.
dp[i][j] = 0 if matrix[i][j] == "0"
dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"

Then loop through matrix
Min Width(has "1"):= Math.min(width, dp[curRow][j]);
Min Height(has "1"):= curRow - i + 1;
MaxArea = Min Width * Min Height``````

Solution:

``````/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
let row = matrix.length;
if (row === 0) return 0;
let col = matrix.length;

// dp[i][j] := max length of all 1s ends with col j at row i.
// dp[i][j] = 0 if matrix[i][j] == "0"
// dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"
let dp = Array.from(new Array(row), () => new Array(col));
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (matrix[i][j] === "1") {
dp[i][j] = j === 0 ? 1 : dp[i][j - 1] + 1;
} else {
dp[i][j] = 0;
}
}
}

let maxArea = 0;
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
let width = Infinity;
for (let curRow = i; curRow < row; curRow++) {
width = Math.min(width, dp[curRow][j]);
if (width === 0) break;
let height = curRow - i + 1;
maxArea = Math.max(maxArea, width * height);
}
}
}
return maxArea;
};``````