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

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