# Find a Peak Element II LeetCode Solution

Difficulty Level Medium
XingViews 22

## Problem Statement

Find a Peak Element II LeetCode Solution – 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-indexed `m 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. ```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.
```

## Explanation

Forgiven `matrix[M][N]`, create a new 1D array `maxPlaneOfCol[N]` which stores the largest number in each column.

For the above matrix, `maxPlaneOfCol = {4, 9, 6, 3, 7, 5}`
Let `maxPlaneOfCol[i]` represent the height of the plane at the index `i`

Now we have reduced the 2D problem to a 1D problem. Using the same logic as in Find Peak Element, we can find the column that has the peak plane. Remember, the elements in `maxPlaneOfCol` represent the largest number of each column. If we find a peak plane at the index, then it means that there is an element  `column# p` that is bigger than all the elements in `column# p-1` and `column# p+1`. Once we have the peak column, we can easily find the `row#` peak element in the `column# p`. Now you have both `row#` and `col#` of a peak element in a 2D array. That’s it !!

To populate `maxPlaneOfCol[N]`, we need to traverse all the columns in the 2D array, which basically means that we have to read all the elements in the 2D array. So, when you are reading the entire 2D array, why not just return the coordinates of the largest number in the 2D array ?!! The largest element is guaranteed to be a peak element, isn’t it !!??

Do we really need to find the `max` in each and every column? Will it is not sufficient to just find the `max` of the `midColumn` ? If we find the `max` of only the `midColumn`, we will calculate `max` of only `log(N)` columns in our entire algorithm.

## Code

### C++ Code For Find a Peak Element II

```class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int startCol = 0, endCol = mat.size()-1;

while(startCol <= endCol){
int maxRow = 0, midCol = startCol + (endCol-startCol)/2;

for(int row=0; row<mat.size(); row++){
maxRow = mat[row][midCol] >= mat[maxRow][midCol]? row : maxRow;
}

bool leftIsBig    =   midCol-1 >= startCol  &&  mat[maxRow][midCol-1] > mat[maxRow][midCol];
bool rightIsBig   =   midCol+1 <= endCol    &&  mat[maxRow][midCol+1] > mat[maxRow][midCol];

if(!leftIsBig && !rightIsBig)          // we have found the peak element
return vector<int>{ maxRow, midCol};

else if(rightIsBig) // if rightIsBig, then there is an element in 'right' that is bigger than all the elements in the 'midCol',
startCol = midCol+1;    //so 'midCol' cannot have a 'peakPlane'

else // leftIsBig
endCol = midCol-1;
}
return vector<int>{-1,-1};
}
};```

### Java Code For Find a Peak Element II

```class Solution {
public int[] findPeakGrid(int[][] mat) {
int startCol = 0, endCol = mat.length-1;

while(startCol <= endCol){
int maxRow = 0, midCol = startCol + (endCol-startCol)/2;

for(int row=0; row<mat.length; row++){
maxRow = mat[row][midCol] >= mat[maxRow][midCol]? row : maxRow;
}

boolean leftIsBig    =   midCol-1 >= startCol  &&  mat[maxRow][midCol-1] > mat[maxRow][midCol];
boolean rightIsBig   =   midCol+1 <= endCol    &&  mat[maxRow][midCol+1] > mat[maxRow][midCol];

if(!leftIsBig && !rightIsBig)   // we have found the peak element
return new int[]{maxRow, midCol};

else if(rightIsBig)  // if rightIsBig, then there is an element in 'right' that is bigger than all the elements in the 'midCol',
startCol = midCol+1; //so 'midCol' cannot have a 'peakPlane'

else // leftIsBig
endCol = midCol-1;
}
return null;
}
}```

### Python Code For Find a Peak Element II

```class Solution(object):
def findPeakGrid(self, mat):
startCol = 0
endCol = len(mat)-1

while startCol <= endCol:
maxRow = 0
midCol = (endCol+startCol)//2

for row in range(len(mat)):
maxRow = row if (mat[row][midCol] >= mat[maxRow][midCol]) else maxRow

leftIsBig    =   midCol-1 >= startCol  and  mat[maxRow][midCol-1] > mat[maxRow][midCol]
rightIsBig   =   midCol+1 <= endCol    and  mat[maxRow][midCol+1] > mat[maxRow][midCol]

if (not leftIsBig) and (not rightIsBig):   # we have found the peak element
return [maxRow, midCol]
elif rightIsBig:             # if rightIsBig, then there is an element in 'right' that is bigger than all the elements in the 'midCol',
startCol = midCol+1     # so 'midCol' cannot have 'peakPlane'
else:                           # leftIsBig
endCol = midCol-1

return []```

## Complexity Analysis for Find a Peak Element II LeetCode Solution

O(M*Long N)

### Space Complexity

O(1) as we are not using any extra space.

Translate »