Find a local minimum in a 2-D array [duplicate]

Question

Given an N-by-N array a of N² distinct integers, design an O(N) algorithm to find a local minimum: an pair of indices i and j such that:

• a[i][j] < a[i+1][j]
• a[i][j] < a[i-1][j]
• a[i][j] < a[i][j+1]
• a[i][j] < a[i][j-1]

I found this question in a an online algorithm book, Introduction to Programming in Java, chapter 4.2: Sorting and Searching.

It is similar to problem 35 (same page):

• Given an array of N real numbers, write a static method to find in logarithmic time a local minimum (an index i such that a[i-1] < a[i] < a[i+1]).

It has some sort of binary search based solution which I am not able to find out.

Answer 1

The same problem is mentioned in web version of book Algorithms by Robert Sedgewick and Kevin Wayne. (See "Creative problems" section, problem 19).

The hint for the problem given by author in that link is:

Find the minimum in row N/2, check neighbors p and q in column, if p or q is smaller then recur in that half.

A better aprroach would be : Find the minimum in row N/2, check all entries in its column, if we get smaller entry in column, then recur in the row where smaller column entry belongs.

eg. For array below, N=5:

1  12  3   1  -23  
7   9  8   5   6
4   5  6  -1  77
7   0  35 -2  -4
6  83  1   7  -6

Step 1: The middle row is [4 5 6 -1 77]. ie. row number 3.

Step 2: Minimum entry in current row is -1.

Step 3: Column neighbors for min entry (ie. -1) are 5 and -2. -2 being the minimum neighbor. Its in the 4th row.

Continue with steps 2-3 till we get the local min.

EDIT:

For example mentioned in comment from @anuja (the main problem is for n-by-n array. This input is 3-by-4 array but we can work with that) :

1 2 3  4 
5 1 6 -1
7 3 4 -2

Step 1: The middle row is [5 1 6 -1]. ie. row number 2.

Step 2: Minimum entry in current row is -1.

Step 3: Column neighbors for min entry (ie. -1) are 4 and -2. -2 is the minimum column neighbor. Its in the 3rd row.

Iterating to Step 2: -2 is smallest in its row and smallest amongst its column neighbours. So we end with -2 as output for local minimum.