2

I was practicing for an interview and I found the following problem on Glassdoor.

Given a board with black (1) and white (0), black are all connected. find the min rectangle that contains all black. An example given is
0 0 0 0 0 
0 1 1 1 0 
0 1 1 0 0 
0 1 0 0 0 
0 0 0 0 0

This problem challenged my understanding of connectedness, will the 1s in the matrix below be considered all connected to each other?

0 0 0 0 0 
0 1 0 1 0 
0 1 0 1 0 
0 1 1 1 0 
0 0 0 0 0

Should I considered 8-connectedness by default?

vkaul11
  • 4,098
  • 12
  • 47
  • 79
  • Connectivity is transitive. If A is connected to B and B is connected to C then A is connected to C. – Dan D. Mar 24 '14 at 02:24
  • 3
    Sorry I can't make sense of your question. What does the interview problem have to do with connectedness? And if it has nothing to do with it, why bring it up at all? – Niklas B. Mar 24 '14 at 04:13

2 Answers2

2

Should I considered 8-connectedness by default?

No, connectivity can be defined in both ways, 4 connected and 8 connected and there is no default definition of connectivity. Moreover, interview questions are mostly understated so you must clarify with your interviewer in case of an ambiguity.

Find the min rectangle that contains all black.

You can replace all the ones with -Infinity and then find the sub rectangle having the maximum sum using Kadane's algorithm for 2D arrays. You will also have to replace the zeros with ones before applying kadane's. For an implementation see this.

Note that whether the blacks are all connected or not, the algorithm to find the maximum sub rectangle containing all 0s remains the same.

Nikunj Banka
  • 11,117
  • 16
  • 74
  • 112
  • "Find the min rectangle that contains all black." You don't need Kadane for that (in fact it doesn't even give you a minimal area solution), just find minimum X, mininmum Y, maximum X and maximum Y of any of the black cells. – Niklas B. Mar 24 '14 at 04:00
  • 1
    Yes, it is huge overkill. But I think it is a cool reduction to a problem we have already solved before. (and may have implemented) – Nikunj Banka Mar 24 '14 at 04:04
  • OK but then you need to figure out how to modify it so that it minimizes the rectangle area in case of ties... The straightforward solution to the problem would be a two line program – Niklas B. Mar 24 '14 at 04:05
  • The question asks to maximize the area of the sub rectangle that contains all 0s. And kadane's algorithm will easily accomplish this. Can you please tell which two line program you are referring to? The best I could google is http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-nn-binary-matrix – Nikunj Banka Mar 24 '14 at 04:10
  • Sorry what? Where does the question ask that? I see no mention of that at all – Niklas B. Mar 24 '14 at 04:11
  • "Find the min rectangle that contains all black." -> xmin/xmax = minimum/maximum x coordinate of a black cell, ymin/ymax = minimum/maximum y coordinate of a black cell -> result is the rectangle with corners (xmin, ymin), (xmax, ymax) – Niklas B. Mar 24 '14 at 04:12
0

This does not answer OP's question, but I think it is interesting.

The first idea that readers got to solve the interview question is to find a rectangle whose edges are aligned with the axes. Note that the "min rectangle" can be the rectangle that minimizes its area, and it doesn't need to be aligned with the axes, it can be rotated. For example:

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

a 4x4 aligned rectangle would contain all the 1's, but a diagonal ~4x1 rectangle too and is smaller.

These cases require the rotating calipers algorithm, or similar.

ChronoTrigger
  • 8,459
  • 1
  • 36
  • 57