Find a Peak Element II
MedPrompt
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.
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.lengthn == mat[i].length1 <= m, n <= 5001 <= mat[i][j] <= 105- No two adjacent cells are equal.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through every cell of the matrix and checking if it's a peak element. A cell is a peak if it is strictly greater than all its four adjacent neighbors (top, bottom, left, and right).
Algorithm
- Iterate through each row
ifrom0tom-1. - Inside the row loop, iterate through each column
jfrom0ton-1. - For the current cell
mat[i][j], get the values of its four neighbors, treating out-of-bounds neighbors as -1. - Check if
mat[i][j]is strictly greater than all four neighbors. - If it is, return the coordinates
[i, j].
Walkthrough
The algorithm iterates through each cell (i, j) from (0, 0) to (m-1, n-1). For each cell mat[i][j], we compare its value with its four neighbors. The neighbors are mat[i-1][j] (top), mat[i+1][j] (bottom), mat[i][j-1] (left), and mat[i][j+1] (right). We must handle boundary conditions. The problem simplifies this by stating the matrix is surrounded by an outer perimeter with the value -1. So, if a neighbor is outside the matrix bounds, its value is considered -1. If mat[i][j] is strictly greater than all its existing neighbors, it is a peak, and we return its coordinates [i, j]. Since the problem guarantees that a peak always exists, this method will eventually find and return one.
class Solution { public int[] findPeakGrid(int[][] mat) { int m = mat.length; int n = mat[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int currentVal = mat[i][j]; int top = (i > 0) ? mat[i - 1][j] : -1; int bottom = (i < m - 1) ? mat[i + 1][j] : -1; int left = (j > 0) ? mat[i][j - 1] : -1; int right = (j < n - 1) ? mat[i][j + 1] : -1; if (currentVal > top && currentVal > bottom && currentVal > left && currentVal > right) { return new int[]{i, j}; } } } return new int[]{-1, -1}; // Should not be reached as per problem statement }}Complexity
Time
O(m * n), where `m` is the number of rows and `n` is the number of columns. In the worst case, we might have to scan the entire matrix.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large matrices and does not meet the time complexity requirement of the problem, which is O(m log(n)) or O(n log(m)).
Solutions
Solution
class Solution { public int [] findPeakGrid ( int [][] mat ) { int l = 0 , r = mat . length - 1 ; int n = mat [ 0 ]. length ; while ( l < r ) { int mid = ( l + r ) >> 1 ; int j = maxPos ( mat [ mid ]); if ( mat [ mid ][ j ] > mat [ mid + 1 ][ j ]) { r = mid ; } else { l = mid + 1 ; } } return new int [] { l , maxPos ( mat [ l ])}; } private int maxPos ( int [] arr ) { int j = 0 ; for ( int i = 1 ; i < arr . length ; ++ i ) { if ( arr [ j ] < arr [ i ]) { j = i ; } } return j ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.