2D Peak Finding Algorithm In O(n) Worst Case Time?

Answer :

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