/85. Maximal Rectangle

85. Maximal Rectangle

Hard
Arrays58.2% acceptance

Given a 2D list of strings representing a binary matrix of size m x n, where each element is either 0 or 1, compute the area of the largest rectangle containing only 1s. Return the area as an integer.

Example 1

Input: [[1,1,0,1],[1,1,1,1],[0,1,1,1]]

Output: 6

Explanation: The largest rectangle of 1s has area 6.

Example 2

Input: [[0,0],[0,0]]

Output: 0

Explanation: No rectangle of 1s exists.

Example 3

Input: [[1,1],[1,1]]

Output: 4

Explanation: The entire matrix is a rectangle of 1s.

Constraints

  • 1 <= len(binary_matrix) <= 200
  • 1 <= len(binary_matrix[0]) <= 200
  • Each element in binary_matrix is either 0 or 1
Python (current runtime)

Case 1

Input: [['1','0','1','1'],['1','1','1','0'],['1','1','0','0']]

Expected: 4

Case 2

Input: [['0','1','0'],['1','1','1'],['0','1','0']]

Expected: 3

Case 3

Input: [['1']]

Expected: 1

Case 4

Input: [['0']]

Expected: 0

Case 5

Input: [['1','0','1'],['1','1','1'],['1','1','1']]

Expected: 6