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)).
This approach uses a divide-and-conquer strategy similar to binary search to find a peak in logarithmic time with respect to one dimension. We can apply binary search on the columns of the matrix. In each step, we reduce the search space (the set of columns) by half.
Algorithm
- Initialize
lowCol = 0andhighCol = n - 1to define the search space for columns. - While
lowCol <= highCol:- Calculate
midCol = lowCol + (highCol - lowCol) / 2. - Find the maximum element in
midCol. Let its row index bemaxRow. - Compare
mat[maxRow][midCol]with its left and right neighbors. - If
mat[maxRow][midCol]is greater than both, it's a peak. Return[maxRow, midCol]. - If the left neighbor is greater, a peak must exist on the left side. Update
highCol = midCol - 1. - Otherwise (the right neighbor is greater), a peak must exist on the right side. Update
lowCol = midCol + 1.
- Calculate
Walkthrough
The core idea is to eliminate half of the columns in each step. We start with a search space covering all columns, from 0 to n-1. In each iteration of the binary search, we pick the middle column, midCol. We then find the row index maxRow of the global maximum element in this midCol. This takes O(m) time. Now, we consider the element mat[maxRow][midCol]. By its definition, it's already greater than its top and bottom neighbors (or they don't exist). We only need to check its left and right neighbors: mat[maxRow][midCol - 1] and mat[maxRow][midCol + 1]. If mat[maxRow][midCol] is greater than both its left and right neighbors, we have found a 2D peak. We can return [maxRow, midCol]. If the left neighbor mat[maxRow][midCol - 1] is greater, it implies that there must be a peak in the left half of the matrix (columns 0 to midCol - 1). This is because we can follow a path of increasing values starting from mat[maxRow][midCol] into the left subgrid, and this path must end at a peak. So, we update our search space to the left half. Similarly, if the right neighbor mat[maxRow][midCol + 1] is greater, we update our search space to the right half (columns midCol + 1 to n-1). We repeat this process until a peak is found.
class Solution { public int[] findPeakGrid(int[][] mat) { int m = mat.length; int n = mat[0].length; int lowCol = 0; int highCol = n - 1; while (lowCol <= highCol) { int midCol = lowCol + (highCol - lowCol) / 2; // Find the row with the maximum element in the middle column int maxRow = 0; for (int i = 1; i < m; i++) { if (mat[i][midCol] > mat[maxRow][midCol]) { maxRow = i; } } int currentVal = mat[maxRow][midCol]; int leftVal = (midCol > 0) ? mat[maxRow][midCol - 1] : -1; int rightVal = (midCol < n - 1) ? mat[maxRow][midCol + 1] : -1; if (currentVal > leftVal && currentVal > rightVal) { // This is a peak because it's the max in its column (so > top/bottom) // and we've checked it's > left/right. return new int[]{maxRow, midCol}; } else if (currentVal < leftVal) { // Peak is in the left half highCol = midCol - 1; } else { // currentVal < rightVal // Peak is in the right half lowCol = midCol + 1; } } return new int[]{-1, -1}; // Should not be reached }}Complexity
Time
O(m log n). The binary search on `n` columns takes `log n` steps. In each step, we find the maximum in a column, which takes O(m) time. Alternatively, one could binary search on rows for an O(n log m) solution.
Space
O(1), as we only use a constant amount of extra space.
Trade-offs
Pros
Highly efficient and meets the problem's time complexity constraints.
Guaranteed to find a peak due to the greedy ascent property.
Cons
Slightly more complex to understand and implement compared to the brute-force approach.
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 ; } }class Solution { public: vector < int > findPeakGrid ( vector < vector < int >>& mat ) { int l = 0 , r = mat . size () - 1 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; int j = distance ( mat [ mid ]. begin (), max_element ( mat [ mid ]. begin (), mat [ mid ]. end ())); if ( mat [ mid ][ j ] > mat [ mid + 1 ][ j ]) { r = mid ; } else { l = mid + 1 ; } } int j = distance ( mat [ l ]. begin (), max_element ( mat [ l ]. begin (), mat [ l ]. end ())); return { l , j }; } };class Solution : def findPeakGrid ( self , mat : List [ List [ int ]]) -> List [ int ]: l , r = 0 , len ( mat ) - 1 while l < r : mid = ( l + r ) >> 1 j = mat [ mid ]. index ( max ( mat [ mid ])) if mat [ mid ][ j ] > mat [ mid + 1 ][ j ]: r = mid else : l = mid + 1 return [ l , mat [ l ]. index ( max ( mat [ l ]))]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.