I have a matrix of dimensions N x M.
Every cell has an integer.
Now, I want for every 'rectangle', to verify that all its corners are not the same.
Example:
This matrix is fine:
This matrix is not:
The naive solution is to check every possible rectangle, therefore $\binom N2\binom M2$ checks.
Is there any way or algorithm that I can use to make less checks?
This was an assignment I had last semester, eventually I used the naive solution, but the question still bothers me...