Find Peak Element II
MediumBinary search across columns
Halve the columns, find the biggest in the middle column, then move toward a taller neighbor.
The idea
Binary search the columns: in the middle column find the row-wise maximum; move toward whichever horizontal neighbour is larger, guaranteeing a 2D peak.
1
2
3
10
4
5
6
7
20
8
9
12
11
30
14
Step 1 of 3. Find a 2D peak (bigger than its 4 neighbours). Binary search on columns.
1/3
Optimal
timeO(rows·log cols)spaceO(1)
Row-max of the mid column.
1let lo = 0, hi = cols - 1;2while (lo <= hi) {3 const mid = (lo + hi) >> 1;4 const row = maxRowInColumn(grid, mid);5 const left = mid ? grid[row][mid - 1] : -1;6 const right = mid < cols - 1 ? grid[row][mid + 1] : -1;7 if (grid[row][mid] > left && grid[row][mid] > right) return [row, mid];8 if (left > grid[row][mid]) hi = mid - 1; else lo = mid + 1;9}Input
- grid
- 3 × 5
Memory
- at
- —
- cells marked
- 0
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- mat = [[1, 4], [3, 2]]
- Output:
- [0, 1]
- Explanation:
- 4 beats both neighbours it has — 1 to its left and 2 below.
Example 2
- Input:
- mat = [[10, 20, 15], [21, 30, 14], [7, 16, 32]]
- Output:
- [1, 1]
- Explanation:
- 30 is larger than 20 above, 16 below, 21 left and 14 right.
Example 3
- Input:
- mat = [[1]]
- Output:
- [0, 0]
- Explanation:
- A single cell has no neighbours to lose to, so it is a peak.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.