LeetCode 85. Maximal Rectangle (javascript)

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[0].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;
};