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