title: Finding local maxima in a 2D array
body: <p>A local maximum in a 2D array can be defined as a value such that all it's 4 neighbours are less than or equal to it, ie, for <code>a[i][j]</code> to be a local maximum, </p>
  
  <pre><code>a[i+1][j] &lt;= a[i][j] 
  &amp;&amp; a[i-1][j] &lt;= a[i][j]
  &amp;&amp; a[i][j+1] &lt;= a[i][j]
  &amp;&amp; a[i+1][j-1] &lt;= a[i][j]
  </code></pre>
  
  <p>I was asked to find all the local maxima in a given 2D array.</p>
  
  <p>The naive way to do this would be to just go through all the elements, and checking whether or not each element is a local maximum. This would be O( n^2 ). I feel that you cannot do better than this, although my friend insists that an asymptotically better algorithm should exist. Any hints ? </p>
  
  <p>I was thinking along the lines of Divide and Conquer, yet I feel that it would be impossible to detect all the local maxima without going through all the numbers, which would necessarily be O( n^2 ). Am I right or am I missing out on something ?</p>