Problem Overview
You are given a 2D matrix mat[][]. The task is to find any peak element.
An element is considered a peak if it satisfies the following condition:
mat[i][j] ≥ all of its four neighbors:
top, bottom, left, and right
Special Cases
For edge or corner elements, missing neighbors are treated as negative infinity.
A peak does not have to be the global maximum; it only needs to be greater than or equal to its neighbors.
Multiple peaks can exist, and returning any one peak is sufficient.
Examples
Example 1
Input
mat = [[10, 20, 15],
[21, 30, 14],
[7, 16, 32]]
Output
true
Explanation
Peak at (1,1) → 30
Neighbors:
Left = 21
Right = 14
Top = 20
Bottom = 16
Peak at (2,2) → 32
Neighbors:
Missing neighbors are treated correctly as negative infinity.
Example 2
Input
mat = [[17, 7],
[11, 10]]
Output
true
Explanation
Peak at (0,0) → 17
Neighbors:
Constraints
1 ≤ n × m ≤ 10^6
-10^6 ≤ mat[i][j] ≤ 10^6
Expected Complexity
Concept and Approach
Naive Approach
Check every element and compare it with all valid neighbors.
Steps
Traverse each cell in the matrix.
Compare it with top, bottom, left, and right neighbors.
If it satisfies the peak condition, return it.
Complexity
O(n × m)
This approach is too slow for large matrices.
Optimized Approach: Binary Search on Columns
Instead of checking every element, perform a binary search on columns.
Main Idea
For a selected middle column:
Find the maximum element in that column.
Compare it with its left and right neighbors.
Decide whether a peak has been found or which direction to move.
Steps
Step 1: Select the Middle Column
mid = (low + high) / 2
Step 2: Find the Maximum Element in the Middle Column
Scan all rows of the middle column and locate the row containing the largest value.
Step 3: Compare with Left and Right Neighbors
Three cases arise:
Case 1: Peak Found
If:
current ≥ left
and
current ≥ right
then the current element is a peak.
Case 2: Larger Element Exists on the Left
If:
left > current
move the search space to the left half.
Case 3: Larger Element Exists on the Right
Otherwise, move the search space to the right half.
Why This Works
A larger neighbor guarantees that a peak exists in that direction.
This property allows binary search to safely discard half of the columns at every step.
Because the matrix is finite, a peak is guaranteed to exist, and the algorithm will eventually find one.
Java Implementation
import java.util.*;
class Solution {
public ArrayList<Integer> findPeakGrid(int[][] mat) {
int n = mat.length;
int m = mat[0].length;
int low = 0, high = m - 1;
while (low <= high) {
int mid = (low + high) / 2;
// Find max element in mid column
int maxRow = 0;
for (int i = 1; i < n; i++) {
if (mat[i][mid] > mat[maxRow][mid]) {
maxRow = i;
}
}
// Handle edge columns safely
int left = (mid - 1 >= 0)
? mat[maxRow][mid - 1]
: Integer.MIN_VALUE;
int right = (mid + 1 < m)
? mat[maxRow][mid + 1]
: Integer.MIN_VALUE;
// Peak condition
if (mat[maxRow][mid] >= left &&
mat[maxRow][mid] >= right) {
ArrayList<Integer> res = new ArrayList<>();
res.add(maxRow);
res.add(mid);
return res;
}
// Move towards larger neighbor
if (left > mat[maxRow][mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return new ArrayList<>(); // fallback (should not happen)
}
}
Dry Run
Input
mat = [[10, 20, 15],
[21, 30, 14],
[7, 16, 32]]
First Iteration
Middle Column
mid = 1
Column values:
20, 30, 16
Maximum element:
30 at row 1
Compare Neighbors
Left = 21
Right = 14
Current = 30
Since:
30 ≥ 21
30 ≥ 14
Peak found at:
(1, 1)
Value:
30
Complexity Analysis
Time Complexity
Binary search is performed on columns.
Number of binary search iterations:
O(log m)
For each iteration, we scan all rows of the selected column:
O(n)
Overall complexity:
O(n log m)
Space Complexity
O(1)
Only a few variables are used.
Key Points
Use Integer.MIN_VALUE for missing neighbors instead of arbitrary values like -1.
Binary search is applied on columns, not rows.
The algorithm searches for a local maximum, not necessarily the global maximum.
A peak is guaranteed to exist in every valid matrix.
Multiple valid peaks may exist; returning any one of them is acceptable.
Pattern Recognition
This problem is closely related to:
Key Takeaway
The 2D Peak Element problem extends the idea of peak finding from a one-dimensional array to a matrix. By applying binary search on columns and selecting the maximum element in the middle column, we can eliminate half of the search space at every step. This reduces the complexity from O(n × m) to O(n log m), making it efficient even for very large matrices.
Summary
To find a peak element in a matrix efficiently, perform binary search on the columns. For each middle column, locate its maximum element and compare it with its left and right neighbors. If it is greater than or equal to both, a peak has been found. Otherwise, move toward the larger neighbor. This divide-and-conquer strategy guarantees a peak in O(n log m) time while using only constant extra space.