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)