I have an N*N matrix (N=2 to 10000) of numbers that may range from 0 to 1000. How can I find the largest (rectangular) submatrix that consists of the same number?
Examples:
or
10 9 9 9 80
5 9 9 9 10
85 86 54 45 45
15 21 5 1 0
5 6 88 11 10
The output should be the area of the submatrix, followed by 1-based coordinates of its top left element. For the examples, it would be (16, 5, 1) and (6, 2, 1), respectively.
This is a classic problem with a classic solution in O(N^2) time and storage where N is the length of the side of the matrix. Clearly for N=10,000, anything much worse than N^2 isn't practical.
If this is homework then I'm reluctant to give you too much of a clue, or mark it duplicate (which I'm pretty sure it is). A key observation, though, is that an O(N^2) solution exists, in fact a solution based on "visiting" each cell of the matrix basically once (although you also have to look at its neighbours).
It's a bottom-up divide-and-conquer approach, if that helps at all. Think about how you might work out the solution for just parts of the matrix, and then how you might use your knowledge of the solution of one or more smaller parts of the matrix, to work out the solution for a larger part.
It's actually simpler to find the largest square sub-matrix: might be easier to think about that first, and then adapt the answer to rectangles.
[Edit: Come to think of it, I'm going to look pretty silly if the answer for squares doesn't adapt to rectangles]