Find a peak element in a 2D array
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[i1][j], A[i+1][j], A[i][j1] 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][mid1] & max >= A[index][pick+1], max is a peak, return max.
 If max < mat[max_index][mid1], 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 == columns1)
return
max;
// If mid column maximum is also peak
if
(max >= arr[max_index][mid1] &&
max >= arr[max_index][mid+1])
return
max;
// If max is less than its left
if
(max < arr[max_index][mid1])
return
findPeakRec(arr, rows, columns, mid  mid/2);
// If max is less than its left
// if (max < arr[max_index][mid+1])
return
findPeakRec(arr, rows, columns, mid+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.
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/findpeakelement2darray/
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide