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.

Examples:

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:

`// Finding peak element in a 2D Array. ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `const` `int` `MAX = 100; ` ` ` `// Function to find the maximum in column 'mid' ` `// 'rows' is number of rows. ` `int` `findMax(` `int` `arr[][MAX], ` `int` `rows, ` `int` `mid, ` `int` `& max) ` `{ ` ` ` `int` `max_index = 0; ` ` ` `for` `(` `int` `i = 0; i < rows; i++) { ` ` ` `if` `(max < arr[i][mid]) { ` ` ` `// Saving global maximum and its index ` ` ` `// to check its neighbours ` ` ` `max = arr[i][mid]; ` ` ` `max_index = i; ` ` ` `} ` ` ` `} ` ` ` `return` `max_index; ` `} ` ` ` `// Function to find a peak element ` `int` `findPeakRec(` `int` `arr[][MAX], ` `int` `rows, ` `int` `columns, ` ` ` `int` `mid) ` `{ ` ` ` `// Evaluating maximum of mid column. Note max is ` ` ` `// passed by reference. ` ` ` `int` `max = 0; ` ` ` `int` `max_index = findMax(arr, rows, mid, max); ` ` ` ` ` `// If we are on the first or last column, ` ` ` `// max is a peak ` ` ` `if` `(mid == 0 || mid == columns - 1) ` ` ` `return` `max; ` ` ` ` ` `// If mid column maximum is also peak ` ` ` `if` `(max >= arr[max_index][mid - 1] && max >= arr[max_index][mid + 1]) ` ` ` `return` `max; ` ` ` ` ` `// If max is less than its left ` ` ` `if` `(max < arr[max_index][mid - 1]) ` ` ` `return` `findPeakRec(arr, rows, columns, mid - ` `ceil` `((` `double` `)mid / 2)); ` ` ` ` ` `// If max is less than its left ` ` ` `// if (max < arr[max_index][mid+1]) ` ` ` `return` `findPeakRec(arr, rows, columns, mid + ` `ceil` `((` `double` `)mid / 2)); ` `} ` ` ` `// A wrapper over findPeakRec() ` `int` `findPeak(` `int` `arr[][MAX], ` `int` `rows, ` `int` `columns) ` `{ ` ` ` `return` `findPeakRec(arr, rows, columns, columns / 2); ` `} ` ` ` `// Driver Code ` `int` `main() ` `{ ` ` ` `int` `arr[][MAX] = { { 10, 8, 10, 10 }, ` ` ` `{ 14, 13, 12, 11 }, ` ` ` `{ 15, 9, 11, 21 }, ` ` ` `{ 16, 17, 19, 20 } }; ` ` ` ` ` `// Number of Columns ` ` ` `int` `rows = 4, columns = 4; ` ` ` `cout << findPeak(arr, rows, columns); ` ` ` `return` `0; ` `} ` |

Output: 21

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.

## leave a comment

## 0 Comments