☕ DSA Java Articles

Topics › Binary Search › BS on 2D Arrays

Find Peak Element - II

Medium TUF ID 65 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n × m grid mat of non-negative integers in which no two adjacent cells are equal (adjacent means sharing an edge). A cell is a peak if its value is strictly greater than each of its four neighbours: up, down, left and right. Cells outside the grid are treated as having value -1, so a border cell only has to beat the neighbours that exist. Return the coordinates {row, col} of any peak. Aim for O(n log m) or O(m log n) time.

Constraints: 1 ≤ n, m ≤ 500, 0 ≤ mat[i][j] ≤ 10^5.

Example 1

mat = [[1, 4],
       [3, 2]]
answer = [0, 1] or [1, 0]     // 4 beats 1 and 2; 3 beats 1 and 2; both are peaks

Example 2

mat = [[10, 20, 15],
       [21, 30, 14],
       [ 7, 16, 32]]
answer = [1, 1] or [2, 2]     // 30 beats 20, 21, 14, 16; 32 beats 14 and 16

Example 3

mat = [[1, 2, 3, 4, 5]]
answer = [0, 4]               // in a single row the only peak is the largest end

Because a grid can have many peaks and any one is accepted, the tests in the Java file verify that each returned cell really is a peak, and only check exact coordinates on grids that have a single peak.

Why a peak always exists

The largest value in the whole grid is a peak: it is at least as large as every neighbour, and since adjacent cells are never equal it is strictly larger. So the answer is never “none”, and the brute force never falls through. The “no two adjacent equal” rule is what makes strict inequalities work throughout; without it a plateau of equal values could have no strict peak at all.

Approach 1: Brute force, test every cell

Intuition. Check the definition directly: for every cell, compare it with its four neighbours, using -1 for positions outside the grid. Return the first cell that wins all four comparisons.

Algorithm.

  1. Write a helper at(r, c) that returns the cell value or -1 outside the grid.
  2. For each cell in row-major order, return it if it is greater than at of all four neighbours.
static int at(int[][] mat, int r, int c) {
    if (r < 0 || r >= mat.length || c < 0 || c >= mat[0].length) return -1;
    return mat[r][c];
}

static boolean isPeak(int[][] mat, int r, int c) {
    int v = mat[r][c];
    return v > at(mat, r - 1, c) && v > at(mat, r + 1, c) && v > at(mat, r, c - 1) && v > at(mat, r, c + 1);
}

static int[] bruteForce(int[][] mat) {
    for (int r = 0; r < mat.length; r++) {
        for (int c = 0; c < mat[0].length; c++) {
            if (isPeak(mat, r, c)) return new int[]{r, c};
        }
    }
    return new int[]{-1, -1};
}

Complexity. Time O(n × m): each cell costs four comparisons. Space O(1).

Approach 2: Hill climbing

Intuition. Stand on any cell. If some neighbour is larger, step onto the largest neighbour. Repeat until no neighbour is larger; by definition you are then standing on a peak. The walk cannot loop, because the value under your feet strictly increases with every step, so no cell is ever visited twice. It therefore ends after at most n × m steps, and in practice usually after very few.

Algorithm.

  1. Start at (0, 0).
  2. Among the four neighbours (out-of-grid positions count as -1), find the largest one that is strictly bigger than the current cell.
  3. If there is none, return the current cell. Otherwise move there and repeat.
static int[] hillClimb(int[][] mat) {
    int r = 0, c = 0;
    int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    while (true) {
        int bestR = r, bestC = c;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (at(mat, nr, nc) > at(mat, bestR, bestC)) { bestR = nr; bestC = nc; }
        }
        if (bestR == r && bestC == c) return new int[]{r, c};   // no neighbour is larger: a peak
        r = bestR; c = bestC;
    }
}

The inner loop starts with the current cell as the best candidate, so it only moves to a neighbour that is strictly larger; at never returns a value larger than a real cell for an out-of-grid position because real values are non-negative and the sentinel is -1.

Complexity. Time O(n × m) in the worst case (a snake-like path that visits most cells), typically far less. Space O(1).

Hill climbing is a genuinely different idea from scanning, and it is the natural generalisation of “walk uphill” that also solves the one-dimensional version. Its weakness is the worst case, which is no better than the brute force. The optimal solution replaces the walk by a binary search.

Approach 3: Optimal, binary search on columns

Intuition. Pick the middle column and find its maximum; say it is at row r. That cell already beats its vertical neighbours (it is the column maximum and adjacent values are distinct). Look at its horizontal neighbours:

Each round halves the number of candidate columns and costs one column scan, giving O(n log m). If n is much bigger than m, do the same with rows and columns swapped for O(m log n).

Algorithm.

  1. Set lo = 0, hi = m − 1.
  2. While lo <= hi: let mid be the middle column and r the row of its maximum.
    • Read left = at(r, mid − 1) and right = at(r, mid + 1).
    • If mat[r][mid] beats both, return {r, mid}.
    • If left is larger, set hi = mid − 1; otherwise set lo = mid + 1.
static int rowOfColumnMax(int[][] mat, int c) {
    int best = 0;
    for (int r = 1; r < mat.length; r++) if (mat[r][c] > mat[best][c]) best = r;
    return best;
}

static int[] optimal(int[][] mat) {
    int m = mat[0].length;
    int lo = 0, hi = m - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int r = rowOfColumnMax(mat, mid);
        int left = at(mat, r, mid - 1), right = at(mat, r, mid + 1);
        if (mat[r][mid] > left && mat[r][mid] > right) return new int[]{r, mid};
        if (left > mat[r][mid]) hi = mid - 1;      // climb towards the larger side
        else lo = mid + 1;
    }
    return new int[]{-1, -1};
}

Dry run on mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], whose only peak is 9 at (2, 2):

lo hi mid column max row r left right decision
0 2 1 8 2 7 9 right is larger: lo = 2
2 2 2 9 2 8 -1 9 beats both: return (2, 2)

On Example 2 the very first probe lands on column 1, whose maximum 30 beats its neighbours 21 and 14, so (1, 1) is returned after one column scan.

Complexity. Time O(n log m): about log2 m rounds, each scanning one column of n cells. Space O(1).

The loop can only exit without returning if the argument above fails, which requires two equal adjacent cells; on valid input the fallback {-1, -1} is never reached.

Edge cases and pitfalls