Find Any Local Maximum in a 2D Matrix

Hard25–30 min

Topics

ArrayMatrixBinary Search

Companies

AmazonGoogleMicrosoft

A cell in a matrix is a peak if it's strictly greater than every neighbor sharing an edge with it (up, down, left, right) — treat a missing neighbor at the matrix's border as negative infinity. Given a matrix where no two edge-adjacent cells are equal, return the position [row, col] of any peak — one is always guaranteed to exist. Solve it in O(m log n) time by binary-searching over columns: find each candidate column's maximum, then let its left/right neighbors tell you which way to move — the same climbing idea as the 1D peak problem, one dimension up.

Test Case 1:

Input:matrix = [[10,20,15],[21,30,14],[7,16,32]]

Output:[1, 1] or [2, 2]

Explanation:mat[1][1]=30 beats its 4 neighbors (20, 14, 21, 16). mat[2][2]=32 beats its neighbors (14, 16) too — both are valid peaks.

Test Case 2:

Input:matrix = [[1, 3, 2]]

Output:[0, 1]

Explanation:3 is greater than both of its row neighbors, and there's no row above or below.

Test Case 3:

Input:matrix = [[5]]

Output:[0, 0]

Explanation:A single cell has no neighbors, so it's trivially a peak.

Constraints

◆1 ≤ matrix.length, matrix[0].length ≤ 100
◆1 ≤ matrix[i][j] ≤ 10⁵
◆No two cells that share an edge have equal values
◆If multiple peaks exist, returning the position of any one of them is accepted

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

matrix (rows separated by ;) — 1-4 rows, 1-6 cols, no two adjacent cells equal

1	class Solution {
2	public int[] findPeakGrid(int[][] mat) {
3	int rows = mat.length, cols = mat[0].length;
4	int loCol = 0, hiCol = cols - 1;
5	while (loCol <= hiCol) {
6	int midCol = loCol + (hiCol - loCol) / 2;
7	int maxRow = 0;
8	for (int i = 1; i < rows; i++) {
9	if (mat[i][midCol] > mat[maxRow][midCol]) maxRow = i;
10	}
11	int left = midCol > 0 ? mat[maxRow][midCol - 1] : -1;
12	int right = midCol < cols - 1 ? mat[maxRow][midCol + 1] : -1;
13	if (mat[maxRow][midCol] > left && mat[maxRow][midCol] > right) {
14	return new int[]{maxRow, midCol};
15	} else if (left > mat[maxRow][midCol]) {
16	hiCol = midCol - 1;
17	} else {
18	loCol = midCol + 1;
19	}
20	}
21	return new int[]{-1, -1};
22	}
23	}
24

↓loCol

↓hiCol

Variables

rows2

cols5

loCol0

hiCol4

INITIALIZE

Binary search on columns [0, 4]: for each candidate column, find its maximum value, then check whether that cell also beats its left/right neighbors.

Step 1 / 3

Approach & Solutions

Brute Force — Check Every Cell's 4 Neighbors

Brute

For every cell, compare it against its up/down/left/right neighbors (treating a missing neighbor at the matrix's edge as -1, which any positive value beats). The first cell that beats all four is a peak. Correct, but it checks every cell instead of using comparisons to steer toward one directly.

TimeO(m × n)

SpaceO(1)

Java

Try it out

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int rows = mat.length, cols = mat[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int up = i > 0 ? mat[i - 1][j] : -1;
                int down = i < rows - 1 ? mat[i + 1][j] : -1;
                int left = j > 0 ? mat[i][j - 1] : -1;
                int right = j < cols - 1 ? mat[i][j + 1] : -1;
                if (mat[i][j] > up && mat[i][j] > down && mat[i][j] > left && mat[i][j] > right) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

Optimal — Binary Search on Columns

Optimal

Binary-search over columns instead of cells. For a candidate column, find its maximum value (scan that one column, O(m)). That cell already beats its up and down neighbors by construction — it only remains to check left and right. If its left neighbor is bigger, a taller peak must exist somewhere in the columns to the left (the same argument as the 1D peak problem, applied column-wise) — search there. Same for the right. Otherwise it's a genuine 2D peak.

TimeO(m log n)