Max Rectangle in Binary Matrix

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

Bonus if you can solve it in O(n^2) or less.

Example :

A : [  1 1 1
       0 1 1
       1 0 0 
    ]

Output : 4 

As the max area rectangle is created by the 2x2 rectangle created by (0,1), (0,2), (1,1) and (1,2)

Interview Code Editor
Hints
  • Hint 1
  • Hint 2
  • Solution Approach
  • Complete Solution
2413 successful submissions.
Asked In:
  • Google
  • Microsoft
Click here to jump start your coding interview preparation