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

Question

I was doing this course on algorithms from MIT. In the very first lecture the professor presents the following problem:-

A peak in a 2D array is a value such that all it's 4 neighbours are less than or equal to it, ie. for

a[i][j] to be a local maximum,

a[i+1][j] <= a[i][j] && a[i-1][j] <= a[i][j] && a[i][j+1] <= a[i][j] && a[i+1][j-1] <= a[i][j]

Now given an NxN 2D array, find a peak in the array.

This question can be easily solved in O(N^2) time by iterating over all the elements and returning a peak.

However it can be optimized to be solved in O(NlogN) time by using a divide and conquer solution as explained here.

But they have said that there exists an O(N) time algorithm that solves this problem. Please suggest how can we solve this problem in O(N) time.

PS(For those who know python) The course staff has explained an approach here (Problem 1-5. Peak-Finding Proof) and also provided some python code in their problem sets. But the approach explained is totally non-obvious and very hard to decipher. The python code is equally confusing. So I have copied the main part of the code below for those who know python and can tell what algorithm is being used from the code.

def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None): # if it's empty, we're done if problem.numRow <= 0 or problem.numCol <= 0: return None subproblems = [] divider = [] if rowSplit: # the recursive subproblem will involve half the number of rows mid = problem.numRow // 2 # information about the two subproblems (subStartR1, subNumR1) = (0, mid) (subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1)) (subStartC, subNumC) = (0, problem.numCol) subproblems.append((subStartR1, subStartC, subNumR1, subNumC)) subproblems.append((subStartR2, subStartC, subNumR2, subNumC)) # get a list of all locations in the dividing column divider = crossProduct([mid], range(problem.numCol)) else: # the recursive subproblem will involve half the number of columns mid = problem.numCol // 2 # information about the two subproblems (subStartR, subNumR) = (0, problem.numRow) (subStartC1, subNumC1) = (0, mid) (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1)) subproblems.append((subStartR, subStartC1, subNumR, subNumC1)) subproblems.append((subStartR, subStartC2, subNumR, subNumC2)) # get a list of all locations in the dividing column divider = crossProduct(range(problem.numRow), [mid]) # find the maximum in the dividing row or column bestLoc = problem.getMaximum(divider, trace) neighbor = problem.getBetterNeighbor(bestLoc, trace) # 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) # 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 # figure out which subproblem contains the largest number we've seen so # far, and recurse, alternating between splitting on rows and splitting # on columns sub = problem.getSubproblemContaining(subproblems, bestSeen) newBest = sub.getLocationInSelf(problem, bestSeen) if not trace is None: trace.setProblemDimensions(sub) result = algorithm4(sub, newBest, not rowSplit, trace) return problem.getLocationInSelf(sub, result) #Helper Method def crossProduct(list1, list2): """ Returns all pairs with one item from the first list and one item from the second list. (Cartesian product of the two lists.) The code is equivalent to the following list comprehension: return [(a, b) for a in list1 for b in list2] but for easier reading and analysis, we have included more explicit code. """ answer = [] for a in list1: for b in list2: answer.append ((a, b)) return answer

Yeah it may be useless, but it is a really good algorithmic question. — Nikunj Banka
– Nikunj Banka, Commented Apr 16, 2014 at 21:24

maxim1000 · Accepted Answer · 2014-04-19 06:42:48Z

Let's assume that width of the array is bigger than height, otherwise we will split in another direction.
Split the array into three parts: central column, left side and right side.
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.

This is O(nlogn) in the following case. There is an NxN matrix. At every recursive call on your algorithm, you compute the maximum value in the column. This happens for logn times. Thus the complexity is O(nlogn). And I think your algorithm is similar to the one on slide 6(courses.csail.mit.edu/6.006/fall11/lectures/lecture1.pdf) . And they have analysed this to be O(nlogn).
Every time the array gets smaller. So it's not n+n+n+... log(n) times. It's n+n/2+n/4+...<2n
I seem to understand the algorithm now and that it will be O(n). But can you please also add a recurrence relation to your answer. That will further clarify that the running time is O(n).
I've added a note about alternating directions, this should clarify the situation. For square array the reccurence relation will be T(n)=T.horiz.(n)+T.vert.(n), T.horiz(n)=T.horiz.(n/2)+O(n) and T.vert.(n)=T.vert.(n/2)+O(n)
This answer is wrong since you are not considering the number of columns and number of rows right. Let n be the number of columns and m be the number of rows, you are adding m+m+m+... for logn times but not n+n+n+.... Thus, the algorithm is actually O(mlogn). When the matrix is n x n, the algorithm is O(nlogn). Lecture video of lecture 1 of MIT 6.006 lecture video on Youtube gives the analysis.

Falcon Lin · Accepted Answer · 2019-09-03 12:29:04Z

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

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

A small correction, implementation step 2 will decrease gradually along the dimension of the matrix. So it is only theta n for the first round, and then goes to theta n/2, n/4, ...

Nikunj Banka · Accepted Answer · 2014-04-19 19:12:37Z

Here is the working Java code that implements @maxim1000 's algorithm. The following code finds a peak in the 2D array in linear time.

import java.util.*; class Ideone{ public static void main (String[] args) throws java.lang.Exception{ new Ideone().run(); } int N , M ; void run(){ N = 1000; M = 100; // arr is a random NxM array int[][] arr = randomArray(); long start = System.currentTimeMillis(); // for(int i=0; i<N; i++){ // TO print the array. // System. out.println(Arrays.toString(arr[i])); // } System.out.println(findPeakLinearTime(arr)); long end = System.currentTimeMillis(); System.out.println("time taken : " + (end-start)); } int findPeakLinearTime(int[][] arr){ int rows = arr.length; int cols = arr[0].length; return kthLinearColumn(arr, 0, cols-1, 0, rows-1); } // helper function that splits on the middle Column int kthLinearColumn(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){ if(loCol==hiCol){ int max = arr[loRow][loCol]; int foundRow = loRow; for(int row = loRow; row<=hiRow; row++){ if(max < arr[row][loCol]){ max = arr[row][loCol]; foundRow = row; } } if(!correctPeak(arr, foundRow, loCol)){ System.out.println("THIS PEAK IS WRONG"); } return max; } int midCol = (loCol+hiCol)/2; int max = arr[loRow][loCol]; for(int row=loRow; row<=hiRow; row++){ max = Math.max(max, arr[row][midCol]); } boolean centralMax = true; boolean rightMax = false; boolean leftMax = false; if(midCol-1 >= 0){ for(int row = loRow; row<=hiRow; row++){ if(arr[row][midCol-1] > max){ max = arr[row][midCol-1]; centralMax = false; leftMax = true; } } } if(midCol+1 < M){ for(int row=loRow; row<=hiRow; row++){ if(arr[row][midCol+1] > max){ max = arr[row][midCol+1]; centralMax = false; leftMax = false; rightMax = true; } } } if(centralMax) return max; if(rightMax) return kthLinearRow(arr, midCol+1, hiCol, loRow, hiRow); if(leftMax) return kthLinearRow(arr, loCol, midCol-1, loRow, hiRow); throw new RuntimeException("INCORRECT CODE"); } // helper function that splits on the middle int kthLinearRow(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){ if(loRow==hiRow){ int ans = arr[loCol][loRow]; int foundCol = loCol; for(int col=loCol; col<=hiCol; col++){ if(arr[loRow][col] > ans){ ans = arr[loRow][col]; foundCol = col; } } if(!correctPeak(arr, loRow, foundCol)){ System.out.println("THIS PEAK IS WRONG"); } return ans; } boolean centralMax = true; boolean upperMax = false; boolean lowerMax = false; int midRow = (loRow+hiRow)/2; int max = arr[midRow][loCol]; for(int col=loCol; col<=hiCol; col++){ max = Math.max(max, arr[midRow][col]); } if(midRow-1>=0){ for(int col=loCol; col<=hiCol; col++){ if(arr[midRow-1][col] > max){ max = arr[midRow-1][col]; upperMax = true; centralMax = false; } } } if(midRow+1<N){ for(int col=loCol; col<=hiCol; col++){ if(arr[midRow+1][col] > max){ max = arr[midRow+1][col]; lowerMax = true; centralMax = false; upperMax = false; } } } if(centralMax) return max; if(lowerMax) return kthLinearColumn(arr, loCol, hiCol, midRow+1, hiRow); if(upperMax) return kthLinearColumn(arr, loCol, hiCol, loRow, midRow-1); throw new RuntimeException("Incorrect code"); } int[][] randomArray(){ int[][] arr = new int[N][M]; for(int i=0; i<N; i++) for(int j=0; j<M; j++) arr[i][j] = (int)(Math.random()*1000000000); return arr; } boolean correctPeak(int[][] arr, int row, int col){//Function that checks if arr[row][col] is a peak or not if(row-1>=0 && arr[row-1][col]>arr[row][col]) return false; if(row+1<N && arr[row+1][col]>arr[row][col]) return false; if(col-1>=0 && arr[row][col-1]>arr[row][col]) return false; if(col+1<M && arr[row][col+1]>arr[row][col]) return false; return true; } }

Collectives™ on Stack Overflow

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

3 Answers 3

11 Comments

1 Comment

Comments

Linked

Hot Network Questions