# Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all local minima in the array?

## 1 Answer

Scan the entire array to check each cell to see whether it is a local minimum.

There's no algorithm that is asymptotically better; this is optimal to within a constant factor. (Proof: if there is any 3x3 region that you haven't looked at, it might contain a local minimum. So any correct algorithm will need to examine at least one cell out of each 3x3 region, i.e., must examine at least 1/9th of the array.)

• So there is only brute-force search possible (use two nested cycles to take each cell and see if it is less than all its 8 neighbors) ? – Vladimir May 24 '18 at 7:11
• @Vladimir, I didn't say that is the only possible algorithm; I said no algorithm can be asymptotically faster (no algorithm can be more than a constant factor faster). So unless small constant factors matter a lot, you might as well use that, as you're not going to find anything that's much faster than that. – D.W. May 24 '18 at 13:20