2D peak reasoning to move to a half

Question

You have a 2D integer matrix given. An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+1][j], A[i][j-1] and A[i][j+1]. For corner elements, missing neighbors are considered of negative infinite value.

If someone has any understanding please share on how it decides which side to pick as that reduces complexity to $O(n \log n)$.

Solution is to consider the middle column, find its 1d maximum, then if it's not the peak, look at left and right side and pick a side which is larger. My doubt is, why is this algorithm correct?

---

Related material:

A) geeks link: https://www.geeksforgeeks.org/find-peak-element-2d-array/

B) mit This was shared in mit slides where it talks about 1d peak and then 2d peak 1) https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

2) its second link gives an working example but not the reasoning http://courses.csail.mit.edu/6.006/fall11/lectures/lecture1.pdf shows a working

C) Stackoverflow There is also a StackOverflow discussion https://stackoverflow.com/questions/23120300/2d-peak-finding-algorithm-in-on-worst-case-time

My doubt is How Can it predict based on seeing left and right element accurately that it has to go to the bigger half. I tried it a lot of times and it always works. So I know it to be true. I then tried to create a counter example but I couldn't .

It's a very old question : I initiated a chat but it didnt helped so asking question here : https://chat.stackoverflow.com/rooms/192196/2d-peak

Answer 1

The point is that we are not trying to find the global maximum element of the array, only a peak (that is, a local maximum).

Let's say that you look at the middle column and find its global maximum, and this maximum is not a peak, because the value to its left is larger. Then you know that the left half of the matrix contains a value that is larger than all of the elements of the middle column. Hence there is always a peak in the left half (for example, the global maximum of the left half, but we do not necessarily search for that).

The values in the right half are irrelevant; they could be larger or smaller, but we don't care. We only want to be sure that we do not recurse into a half that contains 0 peaks.

Answer 2

The algorithm from Geeks starts by finding the maximum element in the middle column (not the 1D-peak). Let us denote this element by $p_m$ and the middle column by $c_m$.

A peak found on the $\min$-side is not guaranteed to be a peak in the initial matrix; consider the case where the peak is found in the cell directly adjacent to $p_m$.

A peak found on the $\max$-side will always be a peak in the initial matrix.

If the peak is found in the column directly adjacent to $c_1$. It must be the maximum element in its column to be declared a peak, and therefore it must be greater than all elements in $c_1$, and thus a global peak.

If the peak is not found in the column adjacent to $c_1$, then it must also be a global peak.