Find all peaks in a matrix NxN

user_5688102 0
Viewed 148

I am trying to create an algorithm using the straightforward approach to find all peaks in a N x N matrix. But I am facing some issues with the corners, the first and last row, and first and last column. I'm considering the problem as it follows:

[ ][c][ ][ ] a is considered a 2d peak
[d][a][e][ ] or a hill iff a >= b,
[ ][b][ ][ ] a >= d, a >=c, a >=e
[ ][ ][ ][ ]

However, when I need to evaluate the corners as the representation bellow, c and d don't exist. I have to evaluate too many conditions in order to get to something more generic. i.e, for the a bellow, I'll need to check if the position a is valid if row-1 < 0, then I wouldn't need to check anything above a and if col-1 < 0 anything is in the left side of a.

[a][e][ ][ ] 
[b][ ][ ][ ] 
[ ][ ][ ][ ] 
[ ][ ][ ][ ]

But when we take a to the other corners or even evaluating the other positions such as e in the example above, I need to certify myself if e is in a valid position where row-1 exists to prevent evaluating that position and get an error (in the example above I'd surely get an error checking if e >= the element in row-1. I've implemented a piece of code considering the corners, lines 0 and n and columns 0 and n but I stopped and started thinking on how to make it more readable and simple.

void find_hill(){
    int i, j;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            //check corners
            if(i-1 < 0){
                if(j-1 < 0){
                   //check if arr[i][j] >= arr at i,j+1 and i+1,j
                }
                if(j+1 > n-1){
                   //check if arr[i][j] >= arr at i,j-1 and i+1,j 
                }
            }                
        }
    }     
}

I would like to discuss how could I come up to a solution here. Where should I start from to get something simple? I've thought somehow using an approach similar to the flood fill, but it fills each position separately, probably it wouldn't work since I'd end up in the same problem!

multidimensional-array matrix search c algorithm
4 Answers

I suggest the following trick: duplicate the first and last rows and columns, as in :

[ ][a][b][c][ ]
[a][a][b][c][c]
[d][d][e][f][f]
[g][g][h][i][i]
[ ][g][h][i][ ]

then just have your loops start at 1 and end at n-1.

user_148705160

Within the scope of algorithms, there are several options.

You can increase the size of a matrix. On theoretical level that is a perfectly acceptable option, as it will only increase the amount of memory and number of computations in proportion to the width of matrix. Practically though, if you're working with relatively small matrices, it might increase their size anywhere up to 9-fold (in case of 1x1 matrix increased to 3x3). If you find this inelegant, you'll find a lot of things inelegant, and "solutions" that avoid this kind of inelegance are usually way more inelegant and troublesome than those things too.

Another option is obviously conditional statements within loop. It's perfect on theoretical level, as it does not increase memory at all and only adds a constant to every loop cycle you've already been doing... And practically it does exactly that, it makes every cycle take additional time to check a conditional, so no matter if you're handling a lot of small matrices, or less but larger, you've made this piece of code perform worse. If that code was or is very likely to be a bottleneck or generator of a lot of performance issues, then this is actually the worst option to pick. If it's unlikely to be any of that, then it's a good choice because it shows your intent in explicit and concise manner. So if it's the best choice is up to the context, and you could induce anger in other programmers by using or not using this solution, depending if it's a part of code they just want to read through fast, or is it the part that profiling shows most responsible for low performance of application.

Finally, you can just write separate portions of code for all special cases - check four corners, four edges and the rest of the matrix separately. This will not cause "unnecessary" usage of memory and will lead to fastest working code. Will look horrible to read compared to the other two options though.

That said, I am not tackling the software engineering side of this story here. You can make each of these options look much better, more readable and/or maintainable with various techniques, like fe. the already mentioned in another answer option to create a get(x,y) function that would validate it's input - a variant of the "conditional within loop" scenario.

user_73025860

this is similar to apply a kernel to an image, like the Sobel filter or others that use a sliding-window approach. Usually, I ignore the borders, but as you want to detect hills on matrix borders you need to identify the window type.

If you don't care about memory copies, you can create a 3x3 window inside the nested for and, if the window is in a corner, fill the corresponding values with the central one. Maybe something like this

int window[3][3];

for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < n; ++j)
    {
        window[1][1] = arr[i][j];
        window[0][1] = (i - 1 < 0) ? window[1][1] : arr[i-1][j];
        window[2][1] = (i == n - 1) ? window[1][1] : arr[i+1][j];

        window[1][0] = (j - 1 < 0) ? window[1][1] : arr[i][j-1];
        window[1][2] = (j == n - 1) ? window[1][1] : arr[i][j+1];

        // Process window
        // ...
    }
}
user_148197330 
void find_hill() {

    int i, j, k, l;
    
    for(i = 0; i < n; i++){
    
        for(j = 0; j < n; j++){
        
            for(k = i-1; k <= i+1; k++) {
                
                for(l = j-1; l <= j+1; l++) {
                    
                    if( k > 0 && k < n && l > 0 && l < n && (i-k)*(j-l) == 0 && arr[i][j] >= arr[k][l] ) {
                        
                        arr[i][j] is a peak;
                    }
                }
            }                
        }
    }     
}

You could also have this condition

if( !(k == i && j == l) && k > 0 && k < n && l > 0 && l < n && (i-k)*(j-l) == 0 && arr[i][j] > arr[k][l] )

With !(k == i && j == l) saving you from running the rest of the condition 1 time out of 9, but adding the weight of having itself runned 9 times out of 9.

In this 1 out of 9 times you would also execute the code inside the condition, so it's probably better to add that !(k == i && j == l)

user_141706860
Related