title: 2D peak finding algorithm in O(n) worst case time?
body: <p>I was doing <a href="http://courses.csail.mit.edu/6.006/fall11/" rel="noreferrer">this</a> course on algorithms from MIT. In the very first lecture the professor presents the following problem:-</p>
  
  <p>A peak in a 2D array is a value such that all it's 4 neighbours are less than or equal to it, ie. for </p>
  
  <p><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>Now given an NxN 2D array, <strong>find a peak</strong> in the array.</p>
  
  <p>This question can be easily solved in <code>O(N^2)</code> time by iterating over all the elements and returning a peak.</p>
  
  <p>However it can be optimized to be solved in <code>O(NlogN)</code> time by using a divide and conquer solution as explained <a href="http://courses.csail.mit.edu/6.006/fall11/lectures/lecture1.pdf" rel="noreferrer">here</a>.</p>
  
  <p>But they have said that there exists an <code>O(N)</code> time algorithm that solves this problem. Please suggest how can we solve this problem in <code>O(N)</code> time.</p>
  
  <p>PS(For those who know python) The course staff has explained an approach <a href="http://courses.csail.mit.edu/6.006/fall11/psets/ps1_solutions.pdf" rel="noreferrer">here</a> (Problem 1-5. Peak-Finding Proof) and also provided some python code in their problem sets. But the approach explained is totally non-obvious and very hard to decipher. The python code is equally confusing. So I have copied the main part of the code below for those who know python and can tell what algorithm is being used from the code.</p>
  
  <pre><code>def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None):
      # if it's empty, we're done 
      if problem.numRow &lt;= 0 or problem.numCol &lt;= 0:
          return None
  
      subproblems = []
      divider = []
  
      if rowSplit:
          # the recursive subproblem will involve half the number of rows
          mid = problem.numRow // 2
  
          # information about the two subproblems
          (subStartR1, subNumR1) = (0, mid)
          (subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1))
          (subStartC, subNumC) = (0, problem.numCol)
  
          subproblems.append((subStartR1, subStartC, subNumR1, subNumC))
          subproblems.append((subStartR2, subStartC, subNumR2, subNumC))
  
          # get a list of all locations in the dividing column
          divider = crossProduct([mid], range(problem.numCol))
      else:
          # the recursive subproblem will involve half the number of columns
          mid = problem.numCol // 2
  
          # information about the two subproblems
          (subStartR, subNumR) = (0, problem.numRow)
          (subStartC1, subNumC1) = (0, mid)
          (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1))
  
          subproblems.append((subStartR, subStartC1, subNumR, subNumC1))
          subproblems.append((subStartR, subStartC2, subNumR, subNumC2))
  
          # get a list of all locations in the dividing column
          divider = crossProduct(range(problem.numRow), [mid])
  
      # find the maximum in the dividing row or column
      bestLoc = problem.getMaximum(divider, trace)
      neighbor = problem.getBetterNeighbor(bestLoc, trace)
  
      # update the best we've seen so far based on this new maximum
      if bestSeen is None or problem.get(neighbor) &gt; problem.get(bestSeen):
          bestSeen = neighbor
          if not trace is None: trace.setBestSeen(bestSeen)
  
      # return when we know we've found a peak
      if neighbor == bestLoc and problem.get(bestLoc) &gt;= problem.get(bestSeen):
          if not trace is None: trace.foundPeak(bestLoc)
          return bestLoc
  
      # figure out which subproblem contains the largest number we've seen so
      # far, and recurse, alternating between splitting on rows and splitting
      # on columns
      sub = problem.getSubproblemContaining(subproblems, bestSeen)
      newBest = sub.getLocationInSelf(problem, bestSeen)
      if not trace is None: trace.setProblemDimensions(sub)
      result = algorithm4(sub, newBest, not rowSplit, trace)
      return problem.getLocationInSelf(sub, result)
  
  #Helper Method
  def crossProduct(list1, list2):
      """
      Returns all pairs with one item from the first list and one item from 
      the second list.  (Cartesian product of the two lists.)
  
      The code is equivalent to the following list comprehension:
          return [(a, b) for a in list1 for b in list2]
      but for easier reading and analysis, we have included more explicit code.
      """
  
      answer = []
      for a in list1:
          for b in list2:
              answer.append ((a, b))
      return answer
  </code></pre>