Find largest intersecting diagonals

Question

This is an interview question:

Given a n by m matrix of bits find the largest X that is formed in the matrix and return the size of the diagonal of that X. An X is defined as 2 equally sized diagonals that share a single 1.

For instance, the matrix:

00100001
00010010
00001100
00001100
00010010
00100001

Will return a size of 1, because the given X is invalid as the middle part does not share a single 1. On the other hand, the following matrix

101
010
101

Will return a value of 3, as the diagonal is 3. Write such program.

I understand the first solution discussed here, but I am wondering if there is a more efficient way to solve this problem. Thoughts?

Answer 1

There is no asymptotic better solution with regards to time complexity. A weaker problem is to check if the matrix contains any 1-cell. For this problem you clearly you have to visit every cell, which gives you O(nxm). Now this is a lower bound to the original problem, which also has O(nxm). Qed.