Find a Peak Element II
Find any cell in a 2D grid that is strictly larger than its four neighbours, by binary searching on columns and comparing each column's maximum with its left and right neighbours.
Problem Understanding
Find a Peak Element II (LeetCode 1901): in an m × n grid where no two adjacent cells are equal, return the position [i, j] of any cell strictly greater than its up, down, left and right neighbours. The grid is surrounded by -1, and the solution must run in O(m log n) or O(n log m).
Examples: mat = [[1,4],[3,2]] → [0,1] or [1,0]; mat = [[10,20,15],[21,30,14],[7,16,32]] → [1,1] or [2,2].
The Intuition: Collapse Each Column to Its Maximum
A column's maximum already beats the cells above and below it, so the 2D problem becomes the 1D one:
- Pick the middle column and find its maximum.
- Look sideways. If a neighbour in the same row is bigger, climbing toward it can never come back, so a peak lies on that side.
- Otherwise the maximum beats all four neighbours: it is a peak.
This is Find Peak Element applied to column maxima, and it uses the same "discard the half that cannot hold the answer" step as Search a 2D Matrix.
Interactive Walkthrough
NUMBERS UNDER A CELL = ROW, COLUMN
ALL COLUMNS
0,0
0,1
0,2
0,3
0,4
0,5
0,6
1,0
1,1
1,2
1,3
1,4
1,5
1,6
2,0
2,1
2,2
2,3
2,4
2,5
2,6
3,0
3,1
3,2
3,3
3,4
3,5
3,6
lo
0
hi
6
mid
:
Peak
:
Search columns 0 to 6. Every cell outside the grid counts as -1
Next
Column 3: its maximum is 49 (row 3), already bigger than the cells above and below
mat
Struck-out columns are ruled out, the tinted column is the middle one and the filled cell is its maximum, compared with the two cells beside it. Try Goes left to see the search move the other way.
Dry Run Table
Input: the default 4 × 7 grid in the walkthrough.
| lo..hi | mid | Column max (row) | Left | Right | Move |
|---|---|---|---|---|---|
| 0..6 | 3 | 49 (3) | 9 | 56 | right |
| 4..6 | 5 | 55 (2) | 59 | 2 | left |
| 4..4 | 4 | 59 (2) | 36 | 55 | peak |
Answer: [2, 4] (value 59).
The Solution Template
Binary search on columns; one O(m) scan per step.
Find a Peak Element II Code
1var findPeakGrid = function(mat) {2 const m = mat.length, n = mat[0].length;3 let lo = 0, hi = n - 1;4 while (lo <= hi) {5 const mid = (lo + hi) >> 1;6 let row = 0;7 for (let r = 1; r < m; r++) if (mat[r][mid] > mat[row][mid]) row = r;8 const left = mid > 0 ? mat[row][mid - 1] : -1;9 const right = mid < n - 1 ? mat[row][mid + 1] : -1;10 if (left > mat[row][mid]) {11 hi = mid - 1;12 } else if (right > mat[row][mid]) {13 lo = mid + 1;14 } else {15 return [row, mid];16 }17 }18 return [-1, -1];19};
Edge Cases & Common Mistakes
- Using any cell of the middle column: only its maximum is guaranteed to beat its vertical neighbours.
- Edges: a missing neighbour counts as -1, so the first or last column can hold the peak.
- One column: its maximum is a peak immediately.
- Moving toward the smaller neighbour: the climb argument only works toward a bigger one.
- Several peaks: any one is accepted; the search returns the first it lands on.
Summary
Binary search on columns: take the middle column's maximum, move toward a bigger left or right neighbour, and stop when neither is bigger. O(m log n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet