Find a Peak Element in a 2D Matrix, thesarfo

An element strictly greater than its top, bottom, left, and right neighbors (missing edges count as -1). Return any one peak. (LeetCode problem)

Brute force: check every cell against its 4 neighbors — O(n × m).

Optimal — binary search on columns: pick the middle column, find its row-max, and check if that value is a peak relative to its horizontal neighbors. If not, move toward whichever neighbor is larger (the peak must be on that side, by a similar mountain-range argument as the 1D case).

class Solution {
    public int[] findPeakElement(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int low = 0, high = cols - 1;

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

            int maxRow = 0;
            for (int i = 1; i < rows; i++) {
                if (matrix[i][mid] > matrix[maxRow][mid]) {
                    maxRow = i;
                }
            }

            int left = (mid > 0) ? matrix[maxRow][mid - 1] : -1;
            int right = (mid < cols - 1) ? matrix[maxRow][mid + 1] : -1;

            if (matrix[maxRow][mid] > left && matrix[maxRow][mid] > right) {
                return new int[]{maxRow, mid};
            }

            if (left > matrix[maxRow][mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return new int[]{-1, -1};
    }
}

Time: O(n × log m) — O(n) to find the column max, O(log m) for the binary search over columns.