Is there any better algorithm than O(m*n) for peak finding in 2D Matrix ?

Revision en1, by nitin12384, 2022-10-10 11:33:42

The task is to find the position of any one peak element in a 2D integer matrix of size $m * n$, if a peak element exists. Adjacent elements are allowed to be equal.

An element is called peak if it is strictly greater than all of its adjacent elements. For element at position $(i,j)$, these elements are considered adjacent if they exist in the matrix :
$(i+1, j)$, $(i-1, j)$, $(i, j+1)$, $(i, j-1)$

Examples of peak:

$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;6$
$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
For this matrix, only one element is peak, element at position $(3,6)$

$2\;4\;5\;5\;4\;2$
$5\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
$2\;4\;5\;7\;4\;2$
For this matrix, there are two peak elements, one at $(2,1)$, and one at $(5,4)$. You can find any one of them.

$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
$2\;4\;5\;5\;4\;2$
For this matrix, There is no peak.

A simple algorithm would be to linearly scan all elements, with the runtime of $O(m*n)$.
Is there any algorithm better than $O(m*n)$?

Some algorithms that don't work in this case.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 nitin12384 2022-10-10 11:33:42 1838 Initial revision (published)