Find a Peak Element II

You are given an m x n grid of integers mat (0-indexed). A cell is a peak if its value is strictly greater than each of its four edge-sharing neighbors — up, down, left, and right.

Two guarantees make life easier:

No two adjacent cells are ever equal, so comparisons never tie.
Imagine the whole grid is wrapped in an invisible border of -1 cells — a border cell only has to beat the neighbors that actually exist inside the grid.

Return the position of any peak as a length-2 array [i, j]. If the grid contains several peaks, any one of them is a correct answer.

Your algorithm must run in O(m log n) or O(n log m) time — a full scan of the grid is too slow in spirit, even if it passes small inputs.

Hints

· Stuck? Reveal one nudge at a time.

You need any peak, not the tallest one. Does an answer always exist? Think about what happens if you keep stepping to a bigger neighbor.

Pick the middle row and find its maximum. That cell already beats its left and right neighbors — only up and down remain to check.

Compare the middle row's maximum with the cell directly below it. If below is bigger, a peak must exist in the bottom half; otherwise the top half. Binary search the rows: O(n log m).

Common doubts

You are not chasing one specific peak; you only need to keep some peak inside the search range. The row max beats its row neighbors for free, and the up/down comparison proves which half of the rows must contain a peak — possibly a different one than you started near, and that is fine.

Binary search never needed sortedness — it needs a test that reliably tells you which half contains an answer. Here the test is comparing the middle row's maximum with the cell below it. Sorted arrays are just the most familiar special case.

It makes every comparison strict, so there is always a clear uphill direction or you are at a peak. With ties allowed, a plateau could hide the peak on the discarded side and the halving argument would break.

Each step strictly increases the value and the grid is finite, so the walk cannot go on forever. Wherever it stops, no neighbor is bigger — by definition, a peak.

Interview follow-ups

· What an interviewer asks next.

Yes — binary search the columns instead: find the max of the middle column and compare it with the cell to its right. Prefer whichever halves the longer dimension: binary search rows when m >= n, columns otherwise, giving O(min(m,n) · log max(m,n)).

It is the same decider lifted a dimension: in 1-D you compare mid with mid+1 and keep the uphill half; in 2-D you first collapse a row to its maximum, then make the identical up/down comparison.

Plateaus appear and the halving proof collapses — a flat middle row tells you nothing about which side hides a peak. In the worst case you must inspect nearly every cell, so O(m·n) becomes unavoidable.

It is correct but only bounded by O(m·n) — the walk can snake through most of the grid. It is a great existence proof and a nice warm-up answer, but it does not meet the required complexity.

Fun facts

Peak finding is a celebrated opening lecture in MIT's algorithms course — it is often the very first example students see of binary search working on completely unsorted data.
The decider trick here — collapse a row to one representative, then compare across rows — reappears in matrix medians, 2-D matrix search, and even in gradient-ascent intuition for optimization.
The greedy walk-uphill argument is a discrete cousin of hill climbing in AI: guaranteed to terminate at a local optimum, with no promise it is the global one.

Asked at

GoogleAmazonMicrosoftUber

Frequently Sometimes Occasionally

Example 1

Input: mat = [[1,4],[3,2]]
Output: [0,1]
Both 4 (at [0,1]) and 3 (at [1,0]) are peaks — either answer is accepted.

Example 2

Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
30 beats 20, 21, 14, and 16, so [1,1] is a peak. 32 at [2,2] is also a peak, so [2,2] would be accepted too.

Constraints

- m == mat.length - n == mat[i].length - 1 <= m, n <= 500 - 1 <= mat[i][j] <= 10^5 - No two adjacent cells are equal.

This problem takes the classic 1-D peak-finding trick and lifts it into two dimensions — and the leap teaches you one of the most transferable ideas in binary search: you can binary-search a dimension even when nothing is sorted, as long as you can decide which half must contain an answer.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search on a predicate. Halving a search range not because the data is sorted, but because a comparison tells you which half is guaranteed to contain an answer.

1-D peak finding. In an array where neighbors never tie, following the uphill direction always leads to a peak — the 1-D version of this exact problem.

2-D grid traversal. Reading a matrix by rows and columns, and checking the four edge-sharing neighbors of a cell.

Understand the problem

Formally: find any cell mat[i][j] that is strictly greater than its existing neighbors mat[i-1][j], mat[i+1][j], mat[i][j-1], mat[i][j+1]. Cells outside the grid count as -1, so a corner cell only needs to beat its two real neighbors. Since mat[i][j] >= 1, the imaginary border never wins a comparison.

Worked example — mat = [[10,20,15],[21,30,14],[7,16,32]]

  10  20  15
  21 [30] 14      30 > 20, 21, 14, 16  → peak at [1,1]
   7  16 [32]     32 > 14, 16          → peak at [2,2]
  answer: [1,1] or [2,2] — either is correct

Clarifying questions

Asking two or three sharp questions before coding shows an interviewer you probe guarantees instead of assuming them.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Can adjacent cells ever be equal?”

No — the statement guarantees strict inequality between neighbors. This matters enormously: it means every comparison has a clear winner, so an uphill direction always exists or you are at a peak. Ties would break the binary-search argument.

“Are all values positive?”

Yes, at least 1. Combined with the imaginary border of -1, border cells never lose to the outside — you only compare against real neighbors.

Output expectations

“If there are multiple peaks, which one should I return?”

Any one. This is a strong hint that a divide-and-conquer approach is intended — algorithms that discard half the grid keep only one of the possible peaks, and that is fine.

Constraints and scale

“How large can the grid be?”

Up to 500 x 500. A full scan is 250,000 cells — actually fast in practice, but the required complexity of O(n log m) tells you the interviewer wants the binary-search insight, not the scan.

The ideal opening — say it like this

Before I start, I want to confirm the key guarantee: no two adjacent cells are equal, so every neighbor comparison is strict.

Since any peak is accepted, I suspect a divide-and-conquer approach that discards half the grid each step.

Let me first state the simple scan for correctness, then improve it to O of n log m with a binary search over rows.

Key observations

1Aha

Walking uphill always ends at a peak

From any cell, if some neighbor is bigger, step to it. Altitude strictly increases with each step, and the grid is finite — so the walk must stop, and it stops exactly at a cell with no bigger neighbor: a peak. This proves a peak always exists, and it is why greedy uphill motion is safe.

2Aha

The maximum of a row beats its left and right neighbors for free

Take any row and find its largest element. Within its own row it already dominates both horizontal neighbors (strictly, thanks to the no-ties guarantee). So a row-maximum only has two directions left to worry about: up and down. You have collapsed a 4-way check into a 2-way check — which smells exactly like 1-D peak finding on the rows.

3Aha

Comparing a row-max with the cell below it tells you which half holds a peak

Look at the middle row and its maximum mat[mid][j]. If the cell below it, mat[mid+1][j], is bigger — then an uphill walk starting there never needs to come back up into rows 0..mid while it can keep climbing, so some peak lives in the bottom half. Otherwise the top half 0..mid must contain a peak by the same argument. One comparison discards half the rows:

 row mid:    ...  [17] ...        17 = max of row mid
 row mid+1:  ...   23  ...        23 > 17 → search rows mid+1..bottom

Repeat: log m halvings, each costing one O(n) row scan → O(n log m) total.

Brute force vs optimal

	Brute force	Optimal
Idea	Check every cell against 4 neighbors	Binary search on rows via row maxima
Time	O(m·n)	O(n log m)
Space	O(1)	O(1)

Both are worth knowing — walk through the full code for each in the Approaches selector below.

Summary

Key takeaway

Binary search does not need sorted data — it needs a decider: one cheap test that tells you which half must contain an answer. Here the decider is “is the max of the middle row smaller than the cell below it?” The same lifted-dimension trick powers many matrix search problems.

lo, hi = 0, m-1
while lo < hi:
    mid = (lo + hi) / 2
    j   = index of max element in row mid
    if mat[mid][j] < mat[mid+1][j]:  lo = mid + 1   # peak below
    else:                            hi = mid        # peak here or above
return [lo, index of max element in row lo]