Find the Peak Element in a 2D Array/Matrix
Given a 2D Array/Matrix, the task is to find the Peak element.
An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom.
- A Diagonal adjacent is not considered a neighbour.
- A peak element is not necessarily the maximal element.
- More than one such element can exist.
- There is always a peak element.
- For corner elements, missing neighbors are considered of negative infinite value.
Examples:
Input: [[10 20 15], [21 30 14], [7 16 32]]
Output: 1, 1
Explanation: The value at index {1, 1} is 30, which is a peak element because all its neighbors are smaller or equal to it. Similarly, {2, 2} can also be picked as a peak.
Input: [[10 7], [11 17]]
Output : 1, 1
Naive Approach to Find Peak Element in Matrix
Iterate through all the elements of the Matrix and check if it is greater/equal to all its neighbors. If yes, return the element.
C++
// Finding peak element in a 2D Array. #include <bits/stdc++.h> using namespace std; vector< int > findPeakGrid(vector<vector< int > > arr) { vector< int > result; int row = arr.size(); int column = arr[0].size(); for ( int i = 0; i < row; i++) { for ( int j = 0; j < column; j++) { // checking with top element if (i > 0) if (arr[i][j] < arr[i - 1][j]) continue ; // checking with right element if (j < column - 1) if (arr[i][j] < arr[i][j + 1]) continue ; // checking with bottom element if (i < row - 1) if (arr[i][j] < arr[i + 1][j]) continue ; // checking with left element if (j > 0) if (arr[i][j] < arr[i][j - 1]) continue ; result.push_back(i); result.push_back(j); break ; } } return result; } // Driver Code int main() { vector<vector< int > > arr = { { 9, 8 }, { 2, 6 } }; vector< int > result = findPeakGrid(arr); cout << "Peak element found at index: " << result[0] << ", " << result[1] << endl; return 0; } // This code is contributed by Yash // Agarwal(yashagarwal2852002) |
Java
import java.util.*; public class Main { public static List<Integer> findPeakGrid( int [][] arr) { List<Integer> result = new ArrayList<>(); int row = arr.length; int column = arr[ 0 ].length; for ( int i = 0 ; i < row; i++) { for ( int j = 0 ; j < column; j++) { // checking with top element if (i > 0 ) if (arr[i][j] < arr[i - 1 ][j]) continue ; // checking with right element if (j < column - 1 ) if (arr[i][j] < arr[i][j + 1 ]) continue ; // checking with bottom element if (i < row - 1 ) if (arr[i][j] < arr[i + 1 ][j]) continue ; // checking with left element if (j > 0 ) if (arr[i][j] < arr[i][j - 1 ]) continue ; result.add(i); result.add(j); break ; } } return result; } public static void main(String[] args) { int [][] arr = { { 9 , 8 }, { 2 , 6 } }; List<Integer> result = findPeakGrid(arr); System.out.println( "Peak element found at index: " + result.get( 0 ) + ", " + result.get( 1 )); } } |
Python3
# Finding a peak element in 2D array def findPeakGrid(arr): result = [] row = len (arr) column = len (arr[ 0 ]) for i in range (row): for j in range (column): # checking with top element if i > 0 : if arr[i][j] < arr[i - 1 ][j]: continue # checking with right element if j < column - 1 : if arr[i][j] < arr[i][j + 1 ]: continue # checking with bottom element if i < row - 1 : if arr[i][j] < arr[i + 1 ][j]: continue # checking with left element if j > 0 : if arr[i][j] < arr[i][j - 1 ]: continue result.append(i) result.append(j) break return result # driver code arr = [[ 9 , 8 ], [ 2 , 6 ]] result = findPeakGrid(arr) print ( "Peak element found at index:" , result) # This code is constributed by phasing17 |
C#
// C# code to find peak element in a 2D array using System; using System.Collections.Generic; class GFG { static int [] findPeakGrid( int [][] arr) { int [] result = new int [2]; int row = arr.Length; int column = arr[0].Length; for ( int i = 0; i < row; i++) { for ( int j = 0; j < column; j++) { // checking with top element if (i > 0) if (arr[i][j] < arr[i - 1][j]) continue ; // checking with right element if (j < column - 1) if (arr[i][j] < arr[i][j + 1]) continue ; // checking with bottom element if (i < row - 1) if (arr[i][j] < arr[i + 1][j]) continue ; // checking with left element if (j > 0) if (arr[i][j] < arr[i][j - 1]) continue ; result[0] = i; result[1] = j; break ; } } return result; } // driver code to test above function public static void Main() { int [][] arr = { new [] { 9, 8 }, new [] { 2, 6 } }; int [] result = findPeakGrid(arr); Console.WriteLine( "Peak element found at index: " + result[0] + "," + result[1]); } } // THIS CODE IS CONTRIBUTED BY YASH // AGARWAL(YASHAGAWRAL2852002) |
Javascript
// Finding a peak element in 2D array function findPeakGrid(arr){ let result = []; let row = arr.length; let column = arr[0].length; for (let i = 0; i<row; i++){ for (let j = 0; j<column; j++){ // checking with top element if (i > 0) if (arr[i][j] < arr[i-1][j]) continue ; // checking with right element if (j < column-1) if (arr[i][j] < arr[i][j+1]) continue ; // checking with bottom element if (i < row-1) if (arr[i][j] < arr[i+1][j]) continue ; // checking with left element if (j > 0) if (arr[i][j] < arr[i][j-1]) continue ; result.push(i); result.push(j); break ; } } return result; } // driver code let arr = [[9,8], [2,6]]; let result = findPeakGrid(arr); console.log( "Peak element found at index: " + result[0] + ", " + result[1]); // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999) |
Peak element found at index: 0, 0
Time Complexity: O(rows * columns)
Auxiliary Space: O(1)
Efficient Approach to Find Peak Element in Matrix
This problem is mainly an extension of Find a peak element in 1D array. We apply similar Binary Search based solution here, as shown below:
- 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][mid+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 implementation of the above algorithm:
C++
// Finding peak element in a 2D Array. #include <bits/stdc++.h> using namespace std; // Finding peak element in a 2D Array. #include <bits/stdc++.h> using namespace std; vector< int > findPeakGrid(vector<vector< int > >& mat) { int stcol = 0, endcol = mat[0].size() - 1; // Starting point & end point of Search Space while (stcol <= endcol) { // Bin Search Condition int midcol = stcol + (endcol - stcol) / 2, ansrow = 0; // "ansrow" To keep the row number of global Peak // element of a column // Finding the row number of Global Peak element in // Mid Column. for ( int r = 0; r < mat.size(); r++) { ansrow = mat[r][midcol] >= mat[ansrow][midcol] ? r : ansrow; } // Finding next Search space will be left or right bool valid_left = midcol - 1 >= stcol && mat[ansrow][midcol - 1] > mat[ansrow][midcol]; bool valid_right = midcol + 1 <= endcol && mat[ansrow][midcol + 1] > mat[ansrow][midcol]; // if we're at Peak Element if (!valid_left && !valid_right) { return { ansrow, midcol }; } else if (valid_right) stcol = midcol + 1; // move the search space in right else endcol = midcol - 1; // move the search space in left } return { -1, -1 }; } // Driver Code int main() { vector<vector< int > > arr = { { 9, 8 }, { 2, 6 } }; vector< int > result = findPeakGrid(arr); cout << "Peak element found at index: " << result[0] << "," << result[1] << endl; return 0; } |
Java
// Finding peak element in a 2D Array. import java.util.*; public class GFG { static int [] findPeakGrid( int [][] mat) { // Starting point & end point of Search Space int stcol = 0 , endcol = mat[ 0 ].length - 1 ; // Bin Search Condition while (stcol <= endcol) { int midcol = stcol + (endcol - stcol) / 2 , ansrow = 0 ; // "ansrow" To keep the row number of global // Peak element of a column // Finding the row number of Global Peak element // in Mid Column. for ( int r = 0 ; r < mat.length; r++) { ansrow = mat[r][midcol] >= mat[ansrow][midcol] ? r : ansrow; } // Finding next Search space will be left or // right boolean valid_left = midcol - 1 >= stcol && mat[ansrow][midcol - 1 ] > mat[ansrow][midcol]; boolean valid_right = midcol + 1 <= endcol && mat[ansrow][midcol + 1 ] > mat[ansrow][midcol]; // if we're at Peak Element if (!valid_left && !valid_right) { return new int [] { ansrow, midcol }; } else if (valid_right) stcol = midcol + 1 ; // move the search space in right else endcol = midcol - 1 ; // move the search space in left } return new int [] { - 1 , - 1 }; } // Driver Code public static void main(String[] args) { int [][] arr = { { 9 , 8 }, { 2 , 6 } }; int [] result = findPeakGrid(arr); System.out.println( "Peak element found at index: " + result[ 0 ] + "," + result[ 1 ]); } } // This code is contributed by Karandeep1234 |
Python3
# Finding peak element in a 2D Array. def findPeakGrid(mat): stcol = 0 endcol = len (mat[ 0 ]) - 1 # Starting po end po of Search Space while (stcol < = endcol): # Bin Search Condition midcol = stcol + int ((endcol - stcol) / 2 ) ansrow = 0 # "ansrow" To keep the row number of global Peak # element of a column # Finding the row number of Global Peak element in # Mid Column. for r in range ( len (mat)): ansrow = r if mat[r][midcol] > = mat[ansrow][midcol] else ansrow # Finding next Search space will be left or right valid_left = midcol - \ 1 > = stcol and mat[ansrow][midcol - 1 ] > mat[ansrow][midcol] valid_right = midcol + \ 1 < = endcol and mat[ansrow][midcol + 1 ] > mat[ansrow][midcol] # if we're at Peak Element if ( not valid_left and not valid_right): return [ansrow, midcol] elif (valid_right): stcol = midcol + 1 # move the search space in right else : endcol = midcol - 1 # move the search space in left return [ - 1 , - 1 ] # Driver Code arr = [[ 9 , 8 ], [ 2 , 6 ]] result = findPeakGrid(arr) print ( "Peak element found at index:" , result) # This code is contributed by phasing17. |
C#
// Finding peak element in a 2D Array. using System; using System.Collections.Generic; public class GFG { static int [] findPeakGrid( int [][] mat) { // Starting point & end point of Search Space int stcol = 0, endcol = mat[0].Length - 1; // Bin Search Condition while (stcol <= endcol) { int midcol = stcol + (endcol - stcol) / 2, ansrow = 0; // "ansrow" To keep the row number of global // Peak element of a column // Finding the row number of Global Peak element // in Mid Column. for ( int r = 0; r < mat.Length; r++) { ansrow = mat[r][midcol] >= mat[ansrow][midcol] ? r : ansrow; } // Finding next Search space will be left or // right bool valid_left = midcol - 1 >= stcol && mat[ansrow][midcol - 1] > mat[ansrow][midcol]; bool valid_right = midcol + 1 <= endcol && mat[ansrow][midcol + 1] > mat[ansrow][midcol]; // if we're at Peak Element if (!valid_left && !valid_right) { return new int [] { ansrow, midcol }; } else if (valid_right) stcol = midcol + 1; // move the search space in right else endcol = midcol - 1; // move the search space in left } return new int [] { -1, -1 }; } // Driver Code public static void Main( string [] args) { int [][] arr = { new [] { 9, 8 }, new [] { 2, 6 } }; int [] result = findPeakGrid(arr); Console.WriteLine( "Peak element found at index: " + result[0] + "," + result[1]); } } // This code is contributed by phasing17 |
Javascript
// Finding peak element in a 2D Array. function findPeakGrid(mat) { let stcol = 0, endcol = mat[0].length - 1; // Starting po end po of Search Space while (stcol <= endcol) { // Bin Search Condition let midcol = stcol + Math.floor((endcol - stcol) / 2), ansrow = 0; // "ansrow" To keep the row number of global Peak // element of a column // Finding the row number of Global Peak element in // Mid Column. for (let r = 0; r < mat.length; r++) { ansrow = mat[r][midcol] >= mat[ansrow][midcol] ? r : ansrow; } // Finding next Search space will be left or right let valid_left = midcol - 1 >= stcol && mat[ansrow][midcol - 1] > mat[ansrow][midcol]; let valid_right = midcol + 1 <= endcol && mat[ansrow][midcol + 1] > mat[ansrow][midcol]; // if we're at Peak Element if (!valid_left && !valid_right) { return [ ansrow, midcol ]; } else if (valid_right) stcol = midcol + 1; // move the search space in right else endcol = midcol - 1; // move the search space in left } return [ -1, -1 ]; } // Driver Code let arr = [[9, 8], [2 ,6]]; let result = findPeakGrid(arr); console.log( "Peak element found at index: " + result[0] + "," + result[1]) // This code is contributed by phasing14. |
Peak element found at index: 0,0
Time Complexity: O(rows * log(columns)). We recur for half the number of columns. In every recursive call, we linearly search for the maximum in the current mid column.
Auxiliary Space: O(columns/2) for Recursion Call Stack