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.)