Peak finding algorithm in 2d-array with complexity O(n)

Question

The question is as the title says. I am trying to figure out if there is a way of finding peak element in 2d-array in O(n) time where n is the length of each side in 2d-array i.e. n^2 total elements.

By definition, "peak" in a 2-d array is an element such that it is >= to all its neighbours (that is elements in up, down, left and right slots).

I read course note at: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf and understood how to do in O(nlogn) but don't seem to quite grasp how to do about O(n).

Could anybody come up with or explain how this problem can solved in O(n)?

Edit: n is the length of each side of the array i.e there are n^2 elements total.

Answer 1

The second algorithm given in the linked PDF is O(n). A "window" is defined to collectively be the boundary (i.e. all four outer edges), middle column and middle row of the current sub-square. Here's a summary of the algorithm:

1. Find maximum value in current window
2. Return it if it's a peak
3. Otherwise, find the larger neighbor of this maximum and recurse in the corresponding quadrant.

As described in the slides, the time complexity is defined by T(n) = T(n/2) + cn (the T(n/2) term is due to the edge length being halved on each recursive step; the cn term is the time required to find the maximum in the current window). Hence, the complexity is O(n).

The correctness of this algorithm is based on several observations that are listed on one of the slides:

If you enter a quadrant, it contains a peak of the overall array

This is basically a generalization of the same 1D argument. You only enter a quadrant when it contains some element greater than all elements on the border. So, either that element will be a peak, or you can keep "climbing up" until you find a peak somewhere in the quadrant.

Maximum element of window never decreases as we descend in recursion

The next window in the recursion always contains the maximum element of the current window, so this is true.

Peak in visited quadrant is also peak in overall array

This follows from the definition of peak, since it only depends on immediate neighbors.