An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+1][j], A[i][j-1] and A[i][j+1]. For corner elements, missing neighbors are considered of negative infinite value.
Input : 10 20 15 21 30 14 7 16 32 Output : 30 30 is a peak element because all its neighbors are smaller or equal to it. 32 can also be picked as a peak. Input : 10 7 11 17 Output : 17
Below are some facts about this problem:
1: A Diagonal adjacent is not considered as neighbor.
2: A peak element is not necessarily the maximal element.
3: More than one such elements can exist.
4: There is always a peak element. We can see this property by creating some matrices using pen and paper.
Method 1: (Brute Force)
Iterate through all the elements of Matrix and check if it is greater/equal to all its neighbors. If yes, return the element.
Time Complexity: O(rows * columns)
Auxiliary Space: O(1)
Method 2 : (Efficient)
This problem is mainly an extension of Find a peak element in 1D array. We apply similar Binary Search based solution here.
- Consider mid column and find maximum element in it.
- Let index of mid column be ‘mid’, value of maximum element in mid column be ‘max’ and maximum element be at ‘mat[max_index][mid]’.
- If max >= A[index][mid-1] & max >= A[index][pick+1], max is a peak, return max.
- If max < mat[max_index][mid-1], recur for left half of matrix.
- If max < mat[max_index][mid+1], recur for right half of matrix.
Below is the C++ implementation of above algorithm:
Time Complexity : O(rows * log(columns)). We recur for half number of columns. In every recursive call we linearly search for maximum in current mid column.
Auxiliary Space : O(columns/2) for Recursion Call Stack
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.