Engaged Employer

## Interview Question

Interview Mountain View, CA

# Find the largest rectangle with all 0s in an matrix with

only 0 and 1.

0

Did not get the right answer in the given time, but tried several approaches.

Interview Candidate on Mar 27, 2013
1

public static int biggestRectangle(Matrix m) { Matrix cache = new Matrix(m.x, m.y); for (int i = 0; i &lt; cache.x; i++) { for (int j = 0; j &lt; cache.y; j++) { int k = 0; while ((i+k &lt; cache.x) && (m.get(i+k,j)) k++; cache.set(i,j,k); } } int biggestRectangle = 0; for (int i = 0; i &lt; cache.x; i++) { for (int j = 0; j &lt; cache.y; j++) { int rowWidth = cache.get(i,j); int height = 1; while (rowWidth &gt; 0) { biggestRectangle = Math.max(biggestRectangle, rowWidth * height); height++; rowWidth = Math.min(rowWidth, cache.get(i,j+height-1)); } } } return biggestRectangle; }

Rahul on May 5, 2013
0

there is a faster solution that takes only O(N) time where N is the number of elements in the matrix but it would be a bit much to code on a whiteboard

Rahul on May 5, 2013