In last post I talked about finding 1-D array peak.

A peak in a 2-D array is an element which has left, right, top and bottom elements lower than it. A simple approach will be to extend the 1-D array approach. Treat each row (or column) as 1-D array, and apply 1-D peak finding algorithm, which we know takes lgN operations. Once we find that we will check if this is 2-D peak as well (a 2-D peak is 1-D peak by default, but not vice versa). If yes, we are good, else continue with next row.

In case we have a N*N 2-D array, above algorithm gives me a time complexity of N*lgN.

Lets improve the above complexity by introducing divide and conquer approach.

1. Divide the matrix (2-D array) into 4 equal parts, divided on mid row and mid column.

2. Find the local peak (highest element) in row and column.

3 a. If local peak is found in horizontal column (we know left and right are small), check if top and bottom are small, if yes current element is 2-D peak, if no, choose the sub matrix which has higher (top or bottom) number than current element.

3 b. If local peak is found in vertical row (we know top and bottom are small), check if right and left are small, if yes current element is 2-D peak, if no, choose the sub matrix which has higher (left or right) number than current element.

4. After 3, we have got a matric of N/4*N/4 size of inital matrix. Repeat from 1 with new matrix.

1 2 **3** 4 5

1 9 **7** 5 3

**2 3 6 5 3**

3 2 **4** 8 1

1 9 **2** 3 7

7 is found as local maximum, but 9 on left is larger so we move ahead

Step 2

1 2 3

1 **9** 7

2 3 6

Repeating steps above give us 2-D peak

Complexity

Step 1: Check N+N elements to find the maximum= T(N/2)+ CN

Step 2: Check N/2+N/2 elements= T(N/4)+C(N/2)+CN

= T(N/8)+C(N/4)+C(N/2)+CN

…

=T(1)+CN(1+1/2+1/4+1/8+….1/N)

we get a geometric series which tends to 1.

Hence overall complexity O(N)