GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #85 - Maximal Rectangle - LeetCode JavaScript Solutions

#85 - Maximal Rectangle

Hard • View on LeetCode • View on GitHub

Array Dynamic Programming Matrix Stack Monotonic Stack

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

Solution

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

  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[0].length; j++) {
      if (matrix[i][j] === '1') {
        let minWidth = matrix[0].length;

        for (let k = i; k < matrix.length && matrix[k][j] === '1'; k++) {
          let width = 0;

          while (width < minWidth && j + width < matrix[0].length && matrix[k][j + width] === '1') {
            width++;
          }

          minWidth = Math.min(minWidth, width);
          maxArea = Math.max(maxArea, minWidth * (k - i + 1));
        }
      }
    }
  }

  return maxArea;
};

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.