Efficient algorithm to find all peaks in a 2d array [duplicate]

Question

Given a matrix M of integers, a peak is an element of the array that is no smaller than its 4 neighbours (up, down, left, right). There is a nice linear time (O(n) for an n by n matrix) algorithm to find a peak, for example in these lecture notes or a slightly simpler O(n log n) time solution in this code.

Say I want to find k peaks, if that many exist. Is there a way to do this in O(n + k) or O(n log n + k) time?

Answer 1

The answer is no. If k > 1 then the worst case performance will be O(n^2).

The problem is with the "if that many exist" part. When the input contains fewer than k peaks, our algorithm can terminate only when we are certain that there are fewer than k peaks to be found. I will prove (below) that we can only be certain there are fewer than k peaks if we have performed O(n^2) comparisons between neighbouring elements.

Proof:

To be certain that an element is not a peak we must compare it to at least one of its neighbours - if that neighbour happens to be bigger then the element is not a peak. If we have not yet compared an element to any of its neighbours then it could still be a peak, and every comparison we do rules out at most one element from being a peak. Knowing that there are fewer than k peaks in our input is equivalent to knowing that there are at least n^2 - k + 1 non-peaks, which requires that we have performed at least n^2 - k + 1 comparisons, which is O(n^2). For k > 1 there exist inputs with < k peaks, and so in the worst case we will have to perform these O(n^2) comparisons before we stop our search.

Note:

The reason this problem does not arise for the case k = 1 is because every input is guaranteed to have at least one peak. We stop the search when we find our first peak, therefore we never have to check that there are no more peaks to find.