3
$\begingroup$

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:
enter image description here
This matrix is not:
enter image description here
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...

  • 1
    There is an $O(N^2 M \log M)$-time algorithm. (Hint: First consider the case of a 2×M matrix.) I do not know if there is a faster one.2012-02-19
  • 0
    I don't think I follow your thought..2012-02-19
  • 0
    Related: [$17x17$ Challenge](http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html).2012-03-16
  • 0
    You shouldn't say "square", it suggests a square. You'd be better off writing "rectangle", because that's what it is.2012-04-15
  • 1
    @PatrickDaSilva thanks, changed.2012-04-15

2 Answers 2