LeetCode 85. Maximal Rectangle

December 10, 2020

The brute force solution takes $\Omega(m^2n^2)$ time since there are $\frac{m(m+1)n(n+1)}{2}$ possible sub-rectangles.

We can do this faster in $O(mn)$ time:

Build a column-wise cumulative sum histogram for each row, e.g. $\begin{bmatrix} 1&1&0&0 \\ 1&0&1&1 \\ \end{bmatrix}$ would become: $\begin{bmatrix} 1&1&0&0 \\ 2&0&1&1 \\ \end{bmatrix}$
For each of the $m$ histograms, find the maximum rectangle in $O(n)$ time using the largest rectangle in histogram algorithm.

from typing import List, Tuple
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.maximalRectangle([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]), 6)
        self.assertEqual(self.s.maximalRectangle([]), 0)
        self.assertEqual(self.s.maximalRectangle([["0"]]), 0)
        self.assertEqual(self.s.maximalRectangle([["1"]]), 1)
        self.assertEqual(self.s.maximalRectangle([["0","0"]]), 0)

    def test_row(self):
        self.assertEqual(self.s.maximalRectangle([["1","0","1","1"]]), 2)

    def test_col(self):
        self.assertEqual(self.s.maximalRectangle([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","0","0","1"],["1","0","0","1","0"]]), 4)
        self.assertEqual(self.s.maximalRectangle([["1","1","1","0","0"],["1","1","1","1","1"],["1","1","0","0","1"],["1","1","0","1","0"]]), 8)

class Solution:

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        # Build histograms
        hists = []
        for r in matrix:
            nums = [int(c) for c in r]
            if hists:
                nums = [hists[-1][i] + nums[i] if nums[i] > 0 else 0 for i in range(len(nums))]
            hists.append(nums)
        # Find max rectangles
        return max([self.largestRectangleArea(h) for h in hists])

    """From the largest rectangle in histogram problem."""
    def _processStack(self, stack: List[Tuple[int, int]], max_height: int) -> Tuple[int, int]:
        # Returns (<max area>, <sum of counts>) for the popped elements.
        area = c = 0
        while stack and (max_height == None or stack[-1][0] > max_height):
            b = stack.pop()
            c += b[1]
            area = max(area, b[0] * c)
        return area, c

    """From the largest rectangle in histogram problem."""
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        area = 0
        for i in range(len(heights)):
            poss, c = self._processStack(stack, heights[i])
            area = max(area, poss)
            if stack and stack[-1][0] == heights[i]:
                stack[-1][1] += c+1
            else:
                stack.append([heights[i], c+1])
        poss, _ = self._processStack(stack, None)
        area = max(area, poss)
        return area

if __name__ == "__main__":
    unittest.main()