1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ 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) ? $\endgroup$ – Vladimir May 24 '18 at 7:11
  • $\begingroup$ @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. $\endgroup$ – D.W. May 24 '18 at 13:20
  • $\begingroup$ There seems to be a better algorithm. See geeksforgeeks.org/find-peak-element-2d-array $\endgroup$ – Tzachi Dar yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.