Google | Phone | Bounding box of connected component
Anonymous User
2700

Q: Given 1) N x N binary (0 or 1) 2D image which has only one connected component of 1s and 2) a pixel (x0, y0) which belongs to the connected component, find the minimum bounding box size.
e.g.

Input:
image=
[[000000],
 [001100],
 [001110],
 [011100],
 [000000]], x0=2, y0=2
Output:
[3,4]

Expected time complexity : better than O(N^2). (I guess O(N logN), but couldn't find a solution.)
Hint : 1D case (e.g. 0001111111000) can be solved by O(log N) using binary search.

Comments (7)