Thread: a matrix problem

The problem is to find a local maximum value in an NxN matrix in O(n) time. A locally maximum value in a matrix is the one who's value is greater than the values of its neighbours i.e. the North, South, East and West elements. (So the elements lying on its diagonals are not its neighbours).

An algo that came to my mind is that, you start with the element at position (1, 1). Compare it to its neighbours. If it is greater than them, we're done. If not, we pick the largest element out of its neighbours, and repeat the process.

How do I show that this can be done in O(n) time?

Originally Posted by mathdigger

The problem is to find a local maximum value in an NxN matrix in O(n) time. A locally maximum value in a matrix is the one who's value is greater than the values of its neighbours i.e. the North, South, East and West elements. (So the elements lying on its diagonals are not its neighbours).

An algo that came to my mind is that, you start with the element at position (1, 1). Compare it to its neighbours. If it is greater than them, we're done. If not, we pick the largest element out of its neighbours, and repeat the process.

How do I show that this can be done in O(n) time?

The problem as I see it is that the entries in the matrix may look like this:

Code:

1 2 3 x x x x x x x x
o o o o o o o o o o x
x x x x x x x x x o x
x o o o o o o o x o x
x o x x x x x o x o x
x o x o o o x o x o x
x o x o x x x o x o x
x o x o o o o o x o x
x o x x x x x x x o x
x o o o o o o o o o x
x x x x x x x x x x x

Here, the o's represent zeros, and the "snake" of x's represents an increasing sequence of numbers starting with 1, 2, 3 as shown, and continuing to increase as the snake coils towards the centre of the matrix. Your algorithm will require you to move along the entire length of the snake, which has O(N^2) elements in it.

In fact, the element at the end of the snake constitutes the only local maximum in the entire matrix, and I don't see any general procedure for locating it in less than O(N^2) moves. (But then I know nothing about algorithms.)

hmm you're right. Ok, what if I put this extra condition that all the entries of the matrix are distinct real numbers > 0 ? Do you think that can help achieve O(n) time somehow?

Originally Posted by mathdigger

Ok, what if I put this extra condition that all the entries of the matrix are distinct real numbers > 0 ? Do you think that can help achieve O(n) time somehow?

That won't help. In the example that I gave above, just replace the o's by distinct positive numbers all less than 1. You are still left with that long snake of increasing numbers.