title: Algorithm for finding saddle-points in a 2-dimensional array
body: <p>I'm looking for an algorithm to find the positions of all saddle points in an NxN matrix. </p>
  
  <p>Searching through other answers on StackOverflow, as well as other sites in general, I've only found solutions regarding saddle points that operate in one direction. That is, I want to find a saddle point that can be a maximum in its row and minimum in its column, or a minimum in its row and maximum in its column.</p>
  
  <p>For example, given:</p>
  
  <pre><code>array = {
  { 10, 15, 20, 15, 10 } 
  { 5, 10, 15, 10, 5 }
  { 0, 5, 10, 5, 0 }
  { 5, 10, 15, 10, 5 }
  { 10, 15, 20, 15, 10 } },
  </code></pre>
  
  <p>the saddle points are the 10's in the corners and the 10 in the middle. </p>
  
  <p>I can find them naively fairly easily, but I wanted something more efficient. I've been told it can be done in O(n^2).</p>
  
  <p>I thought perhaps I could fix the x-coordinate and iterate through the y-coordinate to find all maximums and minimums, then reverse the process by fixing the y-coordinate and iterating through the x-coordinate, but I can't quite visualize it well enough to implement the idea.</p>
  
  <p>Any help would be greatly appreciated.</p>