1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I understand the algorithmic problem you're trying to solve, but it isn't clear what question you have. Do you want to know how solve this in $O(\log n)$? (if this is possible) $\endgroup$ – Discrete lizard Apr 26 at 10:24
  • $\begingroup$ There is an elementary $O(n)$ time algorithm for $n\times n$ grids, though $\endgroup$ – Discrete lizard Apr 26 at 10:28
  • $\begingroup$ It is not possible to solve the problem in time O(log n). I think the question is why the algorithm called "Divide and Conquer #1" in the link B) is correct. That algorithm takes time O(n log n) on a $n \times n$ grid. The slides also discuss a faster algorithm taking time O(n), but OP does not seem to be asking about that. $\endgroup$ – Vincenzo Apr 26 at 10:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand when you said "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." But when you say " Hence there is always a peak in the left half " why is this ?? $\endgroup$ – MAG May 3 at 7:48
  • $\begingroup$ Because in this case the global maximum of the left half must also be a peak. $\endgroup$ – Vincenzo May 3 at 10:07
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.