Find a Peak Element in a 2D Matrix

Problem Overview

You are given a 2D matrix mat[][]. The task is to find any peak element.

An element is considered a peak if it satisfies the following condition:

mat[i][j] ≥ all of its four neighbors:
top, bottom, left, and right

Special Cases

For edge or corner elements, missing neighbors are treated as negative infinity.
A peak does not have to be the global maximum; it only needs to be greater than or equal to its neighbors.
Multiple peaks can exist, and returning any one peak is sufficient.

Examples

Example 1

Input

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

Output

true

Explanation

Peak at (1,1) → 30

Neighbors:

Left = 21
Right = 14
Top = 20
Bottom = 16

Peak at (2,2) → 32

Neighbors:

Left = 16
Top = 14

Missing neighbors are treated correctly as negative infinity.

Example 2

Input

mat = [[17, 7],
       [11, 10]]

Output

true

Explanation

Peak at (0,0) → 17

Neighbors:

Right = 7
Bottom = 11

Constraints

1 ≤ n × m ≤ 10^6
-10^6 ≤ mat[i][j] ≤ 10^6

Expected Complexity

Time Complexity: O(n log m)
Space Complexity: O(1)

Concept and Approach

Naive Approach

Check every element and compare it with all valid neighbors.

Steps

Traverse each cell in the matrix.
Compare it with top, bottom, left, and right neighbors.
If it satisfies the peak condition, return it.

Complexity

O(n × m)

This approach is too slow for large matrices.

Optimized Approach: Binary Search on Columns

Instead of checking every element, perform a binary search on columns.

Main Idea

For a selected middle column:

Find the maximum element in that column.
Compare it with its left and right neighbors.
Decide whether a peak has been found or which direction to move.

Steps

Step 1: Select the Middle Column

mid = (low + high) / 2

Step 2: Find the Maximum Element in the Middle Column

Scan all rows of the middle column and locate the row containing the largest value.

Step 3: Compare with Left and Right Neighbors

Three cases arise:

Case 1: Peak Found

If:

current ≥ left
and
current ≥ right

then the current element is a peak.

Case 2: Larger Element Exists on the Left

If:

left > current

move the search space to the left half.

Case 3: Larger Element Exists on the Right

Otherwise, move the search space to the right half.

Why This Works

A larger neighbor guarantees that a peak exists in that direction.

This property allows binary search to safely discard half of the columns at every step.

Because the matrix is finite, a peak is guaranteed to exist, and the algorithm will eventually find one.

Java Implementation

import java.util.*;

class Solution {
    public ArrayList<Integer> findPeakGrid(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;

        int low = 0, high = m - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            // Find max element in mid column
            int maxRow = 0;
            for (int i = 1; i < n; i++) {
                if (mat[i][mid] > mat[maxRow][mid]) {
                    maxRow = i;
                }
            }

            // Handle edge columns safely
            int left = (mid - 1 >= 0)
                    ? mat[maxRow][mid - 1]
                    : Integer.MIN_VALUE;

            int right = (mid + 1 < m)
                    ? mat[maxRow][mid + 1]
                    : Integer.MIN_VALUE;

            // Peak condition
            if (mat[maxRow][mid] >= left &&
                mat[maxRow][mid] >= right) {

                ArrayList<Integer> res = new ArrayList<>();
                res.add(maxRow);
                res.add(mid);
                return res;
            }

            // Move towards larger neighbor
            if (left > mat[maxRow][mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return new ArrayList<>(); // fallback (should not happen)
    }
}

Dry Run

Input

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

First Iteration

Middle Column

mid = 1

Column values:

20, 30, 16

Maximum element:

30 at row 1

Compare Neighbors

Left  = 21
Right = 14
Current = 30

Since:

30 ≥ 21
30 ≥ 14

Peak found at:

(1, 1)

Value:

Complexity Analysis

Time Complexity

Binary search is performed on columns.

Number of binary search iterations:

O(log m)

For each iteration, we scan all rows of the selected column:

O(n)

Overall complexity:

O(n log m)

Space Complexity

O(1)

Only a few variables are used.

Key Points

Use Integer.MIN_VALUE for missing neighbors instead of arbitrary values like -1.
Binary search is applied on columns, not rows.
The algorithm searches for a local maximum, not necessarily the global maximum.
A peak is guaranteed to exist in every valid matrix.
Multiple valid peaks may exist; returning any one of them is acceptable.

Pattern Recognition

This problem is closely related to:

2D Peak Element
Matrix Peak Finding
Binary Search in 2D
Divide and Conquer on Matrices
Local Maxima in a Grid
Optimized Matrix Search
O(n log m) Search Algorithms

Key Takeaway

The 2D Peak Element problem extends the idea of peak finding from a one-dimensional array to a matrix. By applying binary search on columns and selecting the maximum element in the middle column, we can eliminate half of the search space at every step. This reduces the complexity from O(n × m) to O(n log m), making it efficient even for very large matrices.

Summary

To find a peak element in a matrix efficiently, perform binary search on the columns. For each middle column, locate its maximum element and compare it with its left and right neighbors. If it is greater than or equal to both, a peak has been found. Otherwise, move toward the larger neighbor. This divide-and-conquer strategy guarantees a peak in O(n log m) time while using only constant extra space.