2D Peak Finding in a Matrix

Reported in interviews at Hudson River Trading

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]$:

  1. Let mid = (lo + hi) // 2 and let max_row be the row of the largest value in column mid; call that value val.
  2. Let left = matrix[max_row][mid - 1] (or $-\infty$ if mid == 0) and right = matrix[max_row][mid + 1] (or $-\infty$ if mid == m - 1).
  3. If val >= left and val >= right, return [max_row, mid]. Else if left > val and lo < mid, return helper(lo, mid - 1). Otherwise return helper(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.

Related free problems