Finding local maxima in a 2D array

问题:

A local maximum in a 2D array can be defined as 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]

I was asked to find all the local maxima in a given 2D array.

The naive way to do this would be to just go through all the elements, and checking whether or not each element is a local maximum. This would be O( n^2 ). I feel that you cannot do better than this, although my friend insists that an asymptotically better algorithm should exist. Any hints ?

I was thinking along the lines of Divide and Conquer, yet I feel that it would be impossible to detect all the local maxima without going through all the numbers, which would necessarily be O( n^2 ). Am I right or am I missing out on something ?

回答1:

I am pretty sure this cannot be solved in less than O(n^2) comparisons. Assume a chess board 2d matrix where all the white squares are 1 and blacks are 0. It wiil will have O(n^2) solutions and each solution requires at least one comparison.

回答2:

Just a heads up, local maxima or minima of a 2D grid can be computed in O(nlgn) time using a divide and conquer strategy. This is a slightly better time bound than the brute force algorithm contained in the O(n^2) time complexity class. Furthermore, improvements can be made to the divide and conquer algorithm to obtain an O(n) algorithm for the 2D grid extrema finding.

Check out these notes on the theory behind such peak picking algorithms (I am sure their are more materials out there):

http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

回答3:

Unless your array is square, your solution is actually O(I * J) not O( n^2 ). Strictly speaking you only have N elements in your 2d array thus this solution is O(N). The only way it could be O( n^2 ) is if the array was square such that I = J = N.

Since the compare is <= rather than <, you need still need to check the next element any shortcuts you try will likely be processor specific.

The worst case is that the entire array is a local maxima because the entire array equals the same value.

Thus you must visit every element once, making it O(N)

To improve real world performance in this you would need to use pointers to access you array as in most languages 2d arrays perform considerably worse than 1d arrays.

回答4:

I believe this question can be answered using what is known as adversary arguments, which gives you a lower bound on the number of comparisons.

And in my opinion, you are right.. this would require atleast n^2 comparisons.

回答5:

YOU DO NOT HAVE TO VISIT EVERY ELEMENT:

All you have to do is visualize the grid and you will see that this can be solved in much less than a flat n^2 (or I*J). Here are the optimizations, by level:

1] for an I*J matrix, you need only search (I-2)*(J-2). Why? the borders cannot be maxima because of the undefined elements:

 e.g. grid[0][J] or grid[I][0] could never be maxima. because of the -1 neighbor.

So for a 10 by 12 grid, instead of visiting all 120 elements, we are looking at 80 elements.

2] if grid[I][J] is a maximum, then we can skip all cells adjacent to [I][J] as we continue the search. This will further reduce the number of elements to compare.

Hence, the answer is no, you don't have to visit every element.

回答6:

Above answers just defend a mathematical model.
Which result from a simplistic view of the problem.

If you work as a programmer, you should know what a processor can do. And you should be aware that code runs in a thread. You should wonder if a task is sub-dividable in smaller tasks, so you be able to work it out multi-threaded and get near a 1/total-threads execution speed-up.

The code to do that depends on the language, so I don't provide an example here.

回答7:

You are given an array of size 4 x 4. You will need to do the following task.

1. Fill the array with some random numbers using rand() function.

2. For each cell (i,j) your will need to find the cell with maximum number among all the possible neighbors the cell (i,j) has.

3. Then put that maximum number in the that cell (i,j)

Sample Input:

177 -90 12 7
1 34 43 67
11 11 122 45
6 90 98 93

Sample Output:

34 177 67 67
177 177 122 122
90 122 98 122
90 98 122 122