2D peak finding algorithm in O(n) worst case time?

1. Let's assume that width of the array is bigger than height, otherwise we will split in another direction.
2. Split the array into three parts: central column, left side and right side.
3. Go through the central column and two neighbour columns and look for maximum.
   • If it's in the central column - this is our peak
   • If it's in the left side, run this algorithm on subarray left_side + central_column
   • If it's in the right side, run this algorithm on subarray right_side + central_column

Why this works:

For cases where the maximum element is in the central column - obvious. If it's not, we can step from that maximum to increasing elements and will definitely not cross the central row, so a peak will definitely exist in the corresponding half.

Why this is O(n):

step #3 takes less than or equal to max_dimension iterations and max_dimension at least halves on every two algorithm steps. This gives n+n/2+n/4+... which is O(n). Important detail: we split by the maximum direction. For square arrays this means that split directions will be alternating. This is a difference from the last attempt in the PDF you linked to.

A note: I'm not sure if it exactly matches the algorithm in the code you gave, it may or may not be a different approach.

To see thata(n):

Calculation step is in the picture

To see algorithm implementation:

1) start with either 1a) or 1b)

1a) set left half, divider, right half.

1b) set top half, divider, bottom half.

2) Find global maximum on the divider. [theta n]

3) Find the values of its neighbour. And record the largest node ever visited as the bestSeen node. [theta 1]

# update the best we've seen so far based on this new maximum
if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
    bestSeen = neighbor
    if not trace is None: trace.setBestSeen(bestSeen)

4) check if the global maximum is larger than the bestSeen and its neighbour. [theta 1]

//Step 4 is the main key of why this algorithm works

# return when we know we've found a peak
if neighbor == bestLoc and problem.get(bestLoc) >= problem.get(bestSeen):
    if not trace is None: trace.foundPeak(bestLoc)
    return bestLoc

5) If 4) is True, return the global maximum as 2-D peak.

Else if this time did 1a), choose the half of BestSeen, go back to step 1b)

Else, choose the half of BestSeen, go back to step 1a)

---

To see visually why this algorithm works, it is like grabbing the greatest value side, keep reducing the boundaries and eventually get the BestSeen value.

# Visualised simulation

round1

round2

round3

round4

round5

round6

finally

For this 10*10 matrix, we used only 6 steps to search for the 2-D peak, its quite convincing that it is indeed theta n

---

By Falcon