Find a Peak Element II

medium binary search matrix divide and conquer

Problem

A peak in an m × n grid is a cell strictly greater than its left, right, top, and bottom neighbours; the grid is bordered by virtual -1 cells and no two adjacent cells are equal. Return the coordinates [i, j] of any peak, running in O(m log n) time.

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

Output[1,1]

30 at (1,1) beats all four neighbours (20, 21, 14, 16). 32 at (2,2) is also a valid peak.

Inputmat = [[1,4],[3,2]]

Output[0,1]

4 at (0,1) is a peak; 3 at (1,0) is another acceptable answer.

matrix (rows by ; , cells by ,)

def find_peak_grid(mat):
    m, n = len(mat), len(mat[0])
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        best = 0
        for i in range(m):
            if mat[i][mid] > mat[best][mid]:
                best = i
        if mat[best][mid] < mat[best][mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    best = 0
    for i in range(m):
        if mat[i][lo] > mat[best][lo]:
            best = i
    return [best, lo]

function findPeakGrid(mat) {
  const m = mat.length, n = mat[0].length;
  let lo = 0, hi = n - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    let best = 0;
    for (let i = 0; i < m; i++)
      if (mat[i][mid] > mat[best][mid]) best = i;
    if (mat[best][mid] < mat[best][mid + 1]) lo = mid + 1;
    else hi = mid;
  }
  let best = 0;
  for (let i = 0; i < m; i++)
    if (mat[i][lo] > mat[best][lo]) best = i;
  return [best, lo];
}

int[] findPeakGrid(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        int best = 0;
        for (int i = 0; i < m; i++)
            if (mat[i][mid] > mat[best][mid]) best = i;
        if (mat[best][mid] < mat[best][mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    int best = 0;
    for (int i = 0; i < m; i++)
        if (mat[i][lo] > mat[best][lo]) best = i;
    return new int[]{best, lo};
}

vector<int> findPeakGrid(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        int best = 0;
        for (int i = 0; i < m; i++)
            if (mat[i][mid] > mat[best][mid]) best = i;
        if (mat[best][mid] < mat[best][mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    int best = 0;
    for (int i = 0; i < m; i++)
        if (mat[i][lo] > mat[best][lo]) best = i;
    return {best, lo};
}

Explanation

The clever idea is to binary search on columns while doing a full scan within each candidate column. We keep a column window [lo, hi] and repeatedly inspect the middle column mid.

Inside column mid we find the row best holding that column's maximum value. This cell already dominates its top and bottom neighbours (they are smaller, since it is the column max), so only its left and right neighbours can be larger.

We compare mat[best][mid] with its right neighbour mat[best][mid + 1]. If the right side is taller, a peak is guaranteed in the right half, so we set lo = mid + 1. Otherwise we keep the left half (including mid) with hi = mid. Whichever direction we move, the taller neighbour ensures a peak still lives in the surviving window.

When the window collapses to a single column (lo == hi), the maximum of that column is a peak: it beats its vertical neighbours by being the column max, and it beats both horizontal neighbours because the search never left a taller side behind. We rescan that final column and return [best, lo].

Each iteration halves the number of columns and costs O(m) to scan one column, giving the required O(m log n) running time.

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