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)
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