Find greatest X shape in a binary matrix

Question

I recently had a technical test for a company, and they had, I think, a really interesting problem about recognizing a shape in a binary matrix.

The goal of the exercise was to create an algorithm that could find the biggest X shape in a binary matrix, and return its length. An X is defined in this way : -A X is composed of two diagonals of equal length, that share a unique point. For example :

101
010
101

Contains a valid X of length 3,so the algorithm will return 3.

1001
0110
0110
1001

Doesn't contain any valid X, so the algorithm will return 1,since a 1-length X is a single 1.

I managed to do the exercise, but I implemented a very messy algorithm, with time complexity estimated at O(n3), which is bad and unsuitable for very large matrix. A large part of this complexity is the double for loop I used to go through the matrix.

What could I have done to make a cleaner algorithm? I ask the question out of personal interest, and need to improve my skills and practical thinking.

Answer 1

If you're OK with O(n^2) extra space, then one option is to build two extra arrays: one to record the length of the longest \ shape centered at each cell, one to record the length of the longest /. (You can build each one in O(n^2) time by using a triply-nested loop -- which might sound like O(n^3) time, but the memoization means that you only need to iterate once over any given \ or /, so the innermost loop can be amortized-constant time.) You then iterate over all positions; for any position, the largest X centered at that position has size equal to the lesser of the two matrices' values at that position. Just track the greatest such lesser value, and you're done.

That has worst-case time complexity of O(n^2), which is clearly asymptotically optimal.