### nitin12384's blog

By nitin12384, history, 20 months ago,

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.
• +1

 » 20 months ago, # | ← Rev. 2 →   +28 Let $M(i, j)$ be a matrix which has all elements $0$, except the element at $(i, j)$, which is $1$. Suppose there exists an algorithm that has time complexity $o(mn)$ (not just $O(mn)$). For all $mn$ distinct matrices $M(i, j)$, the answer for them is distinct, so this algorithm should be able to solve the following problem correctly: "given $(i, j)$, $(i', j') \in \{1, \dots, n\} \times \{1, \dots, m\}$, check if these pairs are equal". However, the algorithm makes $o(mn)$ accesses to the matrix, and hence can't distinguish between at least two $M(i, j)$-s for large enough $n, m$.