algorithm - Find local minimum in n x n matrix in O(n) time

Question

So, this is not my home work question, but it is taken from an ungraded homework of the coursera course on algorithms and data structures (which is now complete).

You are given an n by n grid of distinct numbers. A number is a local minimum if it is smaller than all of its neighbors. (A neighbor of a number is one immediately above, below, to the left, or the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(n) comparisons between pairs of numbers. (Note: since there are n² numbers in the input, you cannot afford to look at all of them. Hint: Think about what types of recurrences would give you the desired upper bound.)

Since the numbers are not in any order, I don't see how we can get away with any thing but O(n²) comparisons.

Answer 1

We can adapt Words Like Jared's answer, by looking at how it can go wrong.

The idea in that answer -- which is a good one -- is to "roll downhill". This just means, if you are on an element, check if it is a local minimum. If so, you are done; otherwise, step to the smallest of its nearest neighbors. Eventually this must terminate because every step is to a smaller element, and that cannot go on forever in a finite array.

The problem with this approach is that the "rolling" can meander all over the place:

20 100 12  11 10 100  2
19 100 13 100  9 100  3
18 100 14 100  8 100  4
17  16 15 100  7   6  5

If you start at the upper left and "roll downhill", you will visit around half of the elements in the array. That is too many, so we have to constrain it a bit.

Start by examining the middle column and middle row. Find the smallest element among all of those and start there.

Roll one step "downhill" from there to enter one of the four quadrants. You will enter one of the quadrants, because the adjacent elements in the middle column and/or row are larger, so only one of the two adjacent quadrants could be "downhill".

Now consider what would happen if you "rolled downhill" from there. Obviously, you would eventually reach a local minimum. (We will not actually do this because it would take too long.) But, in the course of rolling around, you would never leave that quadrant... Because to do so, you would have to cross either the middle column or middle row, and none of those elements are smaller than where you started. Therefore that quadrant contains a local minimum somewhere.

Thus, in linear time, we have identified a quadrant that must contain a local minimum, and we have cut n in half. Now just recurse.

This algorithm takes time 2n + 2n/2 + 2n/4 + ..., which equals 4n, which is O(n) so we are done.

Interestingly, we did not use "rolling downhill" very much at all, except for the critical part: Proving that the algorithm works.

[Update]

As Incassator points out, this answer is not entirely correct, because after you "just recurse" you might roll out of the quadrant again...

The simplest fix is to find the smallest element among the middle row, middle column, and boundary before you "roll downhill".