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.
Tags 2d array, algorithm, a easy question

History

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