2D Peak Finding in a Matrix
Problem statement
You are given an $n \times m$ matrix of distinct integers. An element is a local maximum (peak) if it is strictly greater than all of its up/down/left/right neighbors (boundary elements have fewer neighbors).
Design a divide-and-conquer algorithm that finds a peak in $O(n \log m)$ time.
A matrix can have several peaks, so the graded answer is the peak found by this exact column binary search. Define helper(lo, hi) over the column range $[lo, hi]$:
- Let
mid = (lo + hi) // 2and letmax_rowbe the row of the largest value in columnmid; call that valueval. - Let
left = matrix[max_row][mid - 1](or $-\infty$ ifmid == 0) andright = matrix[max_row][mid + 1](or $-\infty$ ifmid == m - 1). - If
val >= leftandval >= right, return[max_row, mid]. Else ifleft > valandlo < mid, returnhelper(lo, mid - 1). Otherwise returnhelper(mid + 1, hi).
Start with helper(0, m - 1) and return the peak as a list [row, col].
Constraints:
- $1 \leq n, m \leq 10^4$
- All entries are distinct integers
- Only up/down/left/right adjacency counts (no diagonals)
Example 1:
Input:
[[10, 8, 7, 6],
[14, 13, 12, 11],
[15, 9, 1, 21],
[16, 17, 19, 20]]
Output: [2, 3] # value 21
Column 1 has maximum 17 at row 3; its right neighbor 19 is larger, so search columns 2..3. Column 2 has maximum 19 at row 3; its right neighbor 20 is larger, so search column 3. Column 3 has maximum 21 at row 2, which beats its left neighbor 1, so return [2, 3].
Example 2:
Input:
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Output: [2, 2] # value 9 (neighbors 6 and 8)
Example 3:
Input: [[3, 1, 2]]
Output: [0, 0] # value 3
Column 1 holds 1, and its left neighbor 3 is larger, so search column 0, whose maximum 3 is a peak. The value 2 at [0, 2] is also a peak, but the recipe returns [0, 0].
Follow-up: Prove correctness using a "greedy ascent" invariant, and discuss how to handle plateaus if entries are not necessarily distinct.
Show hint
How do you find a peak in a one-dimensional array in logarithmic time, and what single value per column would let you reuse that?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.