A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.
Given a 0-indexedm x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].
You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.
You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.
Example 1:
Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.
Example 2:
Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 500
1 <= mat[i][j] <= 105
No two adjacent cells are equal.
Intuition
Approach:
Similar to Find Peak 1,
Here we find the max element in a particular column
Now this max element we compare with
Left and Right element , because top and bottom need not be compared as maximum
Now based on left and right, change the low and high pointers
Links
Video Links
Approach 1:
N*M*4
C++
class Solution {
public:
bool check(int nrow, int ncol, int m, int n){
return nrow<m and nrow>=0 and ncol<n and ncol>=0;
}
vector<int> findPeakGrid(vector<vector<int>>& arr) {
int m=arr.size(), n=arr[0].size();
int drow[] = {-1,1,0,0};
int dcol[] = {0,0,1,-1};
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
int num = arr[i][j];
bool flag = true;
for(int k=0; k<4; k++){
int nrow = drow[k] + i;
int ncol = dcol[k] + j;
if(check(nrow, ncol, m, n) and num<arr[nrow][ncol]){
flag = false;
break;
}
}
if(flag == true)
return {i,j};
}
}
return {-1,-1};
}
};
Approach 2:
NlogM
C++
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
int low = 0, high = m-1;
while(low <= high){
int maxRow = 0;
int midCol = (low+high) >> 1;
for(int row=0; row<n; row++){
if(mat[row][midCol] > mat[maxRow][midCol]){
maxRow = row;
}
}
int currElement = mat[maxRow][midCol];
int leftElement = midCol == 0 ? -1 : mat[maxRow][midCol-1];
int rightElement = midCol == m-1 ? -1 : mat[maxRow][midCol+1];
if(currElement > leftElement && currElement > rightElement)
return {maxRow, midCol};
else if(currElement < leftElement)
high = midCol - 1;
else
low = midCol + 1;
}
return {-1, -1};
}
};
