Maximal Rectangle

January 11th, 2026

Description

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 = [["0"]]
Output: 0

Example 3:

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

Constraints:

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

Solutions

Identical to Solution 6 with functionally equivalent monotonic stack logic but using more conventional variable naming (m and n for matrix dimensions). It efficiently processes each row's cumulative height histogram in a single pass by maintaining an increasing-height stack, popping and computing areas whenever the monotonic property is violated.

Language: javascript(2026-01-11 10:17)DONE

CPU Performance91.70%

Memory Performance90.83%

/**
 * @param {string[][]} matrix
 * @return {number}
 */
function maximalRectangle(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const heights = new Array(n).fill(0);
    let maxArea = 0;

    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            heights[col] = matrix[row][col] === "1" ? heights[col] + 1 : 0;
        }

        const cols = [];
        let col = 0;
        while (col < n || cols.length > 0) {
            if (
                col < n &&
                (cols.length === 0 ||
                    heights[col] >= heights[cols[cols.length - 1]])
            ) {
                cols.push(col);
                col++;
                continue;
            }

            const height = heights[cols.pop()];
            let width = col - cols[cols.length - 1] - 1;
            if (cols.length === 0) {
                width = col;
            }

            maxArea = Math.max(maxArea, height * width);
        }
    }

    return maxArea;
}

Description

Solutions

AI Explanation