Find Peak Element - II
MetaThe problem
Given a 0-indexed n x m matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the array [i, j].A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbours to the left, right, top, and bottom.
Assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.
Note: As there can be many peak values, 1 is given as output if the returned index is a peak number, otherwise 0.
Input: mat=[[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 neighbours are smaller or equal to it. Similarly, {2, 2} can also be picked as a peak.
Input: mat=[[10, 7], [11, 17]] Output : [1, 1] Explanation:The value at index [1, 1] is 17, which is the only peak element because all its neighbours are smaller or equal to it.
Input: mat=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
- n == mat.length
- m == mat[i].length
- 1 <= m, n <= 500
- 1 <= mat[i][j] <= 105
- No two adjacent cells are equal
cpp
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
}
};java
class Solution {
public int[] findPeakGrid(int[][] mat) {
}
}python
class Solution:
def findPeakGrid(self, mat):javascript
class Solution {
findPeakGrid(mat) {
}
}csharp
public class Solution {
public int[] FindPeakGrid(int[][] mat) {
}
}go
func findPeakGrid(mat [][]int) []int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Binary-search columns.
- 02Find the maximum element in the middle column.
- 03Compare it with horizontal neighbors.
- 04Move toward the larger neighbor.
- 05Return the column maximum when it exceeds both neighbors.
Reference answer
Then expect these follow-ups
What is the simpler `O(RC)` scan?
Tests: baseline reasoning
Why do distinct adjacent values matter?
Tests: proof
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question