Interview Question

Interview Mountain View, CA

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

  only 0 and 1.
Answer

Interview Answer

3 Answers

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 < cache.x; i++) { for (int j = 0; j < cache.y; j++) { int k = 0; while ((i+k < cache.x) && (m.get(i+k,j)) k++; cache.set(i,j,k); } } int biggestRectangle = 0; for (int i = 0; i < cache.x; i++) { for (int j = 0; j < cache.y; j++) { int rowWidth = cache.get(i,j); int height = 1; while (rowWidth > 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.