Google Interview Question: Find the largest rectangle wi... | Glassdoor

Interview Question

Intern Interview Mountain View, CA

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

  only 0 and 1.

Interview Answer

3 Answers


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

Interview Candidate on Mar 27, 2013

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

Rahul on May 5, 2013

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.