🧱 Beginner-Friendly Guide 'Maximal Rectangle' – LeetCode 85 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given

• A 2‑D binary matrix filled with characters '0' and '1'.

Your goal

• Find the largest rectangle containing only '1's and return its area.

Example

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 picture above.

Intuition

Checking every possible rectangle directly is infeasible.
Instead, treat each row as the ground and compute the height of consecutive '1's stacked above it.
Each row then becomes a histogram.

If we can find the largest rectangle in a histogram, we can repeat the process for every row.
A monotonic stack gives us the needed information in linear time:

For a bar at index i:

width  = NSE[i] - PSE[i] - 1
area   = heights[i] * width

The maximum area over all rows is the answer.

Code Blocks

C++ Solution

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        if (matrix.empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();

        vector heights(m, 0), pse(m), nse(m);
        stack ps, ns;
        int max_area = 0;

        for (int i = 0; i  heights[j]) {
                    nse[ns.top()] = j;
                    ns.pop();
                }
                ns.push(j);

                while (!ps.empty() && heights[ps.top()] >= heights[j]) {
                    ps.pop();
                }
                pse[j] = (ps.empty() ? -1 : ps.top());
                ps.push(j);
            }

            // Update max area for this histogram
            for (int j = 0; j  int:
        if not matrix:
            return 0

Python (partial snippet)

int:
    if not matrix:
        return 0

Python Solution

def maximalRectangle(matrix):
    if not matrix:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    max_area = 0

    for i in range(rows):
        # Update heights based on the current row
        for j in range(cols):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0

        # Largest Rectangle in Histogram for this row
        stack = []
        pse = [-1] * cols
        nse = [cols] * cols

        # Next Smaller Element
        for j in range(cols):
            while stack and heights[stack[-1]] > heights[j]:
                nse[stack.pop()] = j
            stack.append(j)

        # Previous Smaller Element (backwards pass)
        stack.clear()
        for j in range(cols - 1, -1, -1):
            while stack and heights[stack[-1]] > heights[j]:
                pse[stack.pop()] = j
            stack.append(j)

        # Compute area for each bar
        for j in range(cols):
            area = heights[j] * (nse[j] - pse[j] - 1)
            max_area = max(max_area, area)

    return max_area

JavaScript Solution (Version 1)

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

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (let i = 0; i  heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Previous Smaller Element (reverse pass)
        stack.length = 0; // clear stack
        for (let j = cols - 1; j >= 0; --j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute area for each bar
        for (let j = 0; j  heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Reset stack for PSE
        stack.length = 0;
        for (let j = cols - 1; j >= 0; j--) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute max area for this row
        for (let j = 0; j < cols; j++) {
            maxArea = Math.max(maxArea, heights[j] * (nse[j] - pse[j] - 1));
        }
    }

    return maxArea;
}

JavaScript Solution (Version 2)

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

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (let i = 0; i < rows; ++i) {
        // Update heights
        for (let j = 0; j < cols; ++j) {
            heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
        }

        // Compute NSE
        const nse = new Array(cols).fill(cols);
        const stack = [];
        for (let j = 0; j < cols; ++j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute PSE
        const pse = new Array(cols).fill(-1);
        stack.length = 0;
        for (let j = cols - 1; j >= 0; --j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Calculate max area for this row
        for (let j = 0; j < cols; ++j) {
            maxArea = Math.max(maxArea, heights[j] * (nse[j] - pse[j] - 1));
        }
    }

    return maxArea;
}

Key Takeaways

• Problem Reduction: Learning to see a 2‑D problem as a sequence of 1‑D problems (histograms) is a powerful mental model.
• Monotonic Stacks: These are essential for finding the “nearest smaller” or “nearest larger” elements in O(n) time.
• Space‑Time Trade‑off: By using O(n) extra space for heights and stacks, we achieve a total time complexity of O(m × n), which is much faster than a brute‑force approach.

Final Thoughts

This problem is a staple in high‑level technical interviews because it combines several layers of logic. In real‑world engineering, these techniques are used in:

• Computer Vision – for object detection.
• Database Optimization – for finding contiguous blocks of free space.
• UI Rendering – for layout engines.

Mastering the monotonic stack will make you a much more formidable problem solver.