Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:


Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Starter code: class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        

Solutions:
class Solution:

	def maximalRectangle(self, matrix):
		if not matrix or not matrix[0]:
			return 0
		n = len(matrix[0])
		height = [0] * (n + 1)
		ans = 0
		for row in matrix:
			for i in range(n):
				height[i] = height[i] + 1 if row[i] == '1' else 0
			stack = [-1]
			for i in range(n + 1):
				while height[i] < height[stack[-1]]:
					h = height[stack.pop()]
					w = i - 1 - stack[-1]
					ans = max(ans, h * w)
				stack.append(i)
		return ans


class Solution:

	def maximalRectangle(self, matrix):
		if not matrix:
			return 0
		m = len(matrix)
		n = len(matrix[0])
		ans = 0
		heights = [0] * (n + 1)
		for i in range(m):
			for j in range(n):
				heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
			stack = [-1]
			for i in range(n + 1):
				while heights[i] < heights[stack[-1]]:
					h = heights[stack.pop()]
					w = i - stack[-1] - 1
					ans = max(ans, w * h)
				stack.append(i)
		return ans


class Solution:

	def __init__(self):
		self.maxarea = 0

	def maximalRectangle(self, matrix):
		if len(matrix) == 0 or len(matrix[0]) == 0:
			return 0

		def maxrect(height):
			height.append(0)
			stack = [-1]
			ans = 0
			for i in range(len(height)):
				while height[i] < height[stack[-1]]:
					h = height[stack.pop()]
					w = i - stack[-1] - 1
					ans = max(ans, h * w)
				stack.append(i)
			height.pop()
			return ans
		abs_max = 0
		height = [0] * len(matrix[0])
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == '0':
					height[j] = 0
				else:
					height[j] += 1
			local_max = maxrect(height)
			if local_max > abs_max:
				abs_max = local_max
		return abs_max