Show problems as
Classic problem #1901MediumArrayBinary SearchMatrix

Find a Peak Element II

Real-world version: Any Summit in a Height Field
Tracked in this browser only
Read Find a Peak Element II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A height field is stored in mat, where mat[r][c] is the altitude of cell r, c. No two cells that share an edge hold the same altitude.

A cell is a summit when its altitude is strictly above the altitude of every cell sharing an edge with it. Cells on the border have fewer neighbours to beat, and everything off the edge of the field counts as lower than any cell, so a summit always exists.

Return the position of a summit as the pair [r, c]. When the field holds more than one summit, any one of them is accepted.

Aim for a routine that does not look at every cell: a running time on the order of rows * log(columns) or columns * log(rows) is expected.

Examples

Example 1

Input
mat = [[1, 4, 3]]
Output
[0, 1]

Cell 0, 1 holds 4, which is above both 1 and 3, and it is the only summit in this field.

Example 2

Input
mat = [[5, 8, 6], [9, 20, 4]]
Output
[1, 1]

Cell 1, 1 holds 20 and beats 8 above it, 9 to its left and 4 to its right, so it is a summit.

Example 3

Input
mat = [[10, 2, 9], [3, 1, 4], [8, 5, 7]]
Output
[0, 0]

Cell 0, 0 holds 10 and beats 2 to its right and 3 below it. The cells at 0, 2 and at 2, 0 and at 2, 2 are summits too, so any of those four answers is accepted.

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 500
  • 1 <= mat[i][j] <= 10^5
  • No two cells sharing an edge hold equal altitudes.

More than one answer is valid. Return any one of them.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_peak_grid(mat: list[list[int]]) -> list[int]:
Java
public int[] findPeakGrid(int[][] mat)

More on the same topics