1901. Find a Peak Element II

Description

A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.

Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j].

You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.

You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.

 

Example 1:

Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.

Example 2:

Input: mat = [[10,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 105
• No two adjacent cells are equal.

 

Solutions

Solution: Binary Search

• Time complexity: O(mlog(n))
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
const findPeakGrid = function (mat) {
  const m = mat.length;
  const n = mat[0].length;
  let left = 0;
  let right = n - 1;

  while (left <= right) {
    const col = Math.floor((left + right) / 2);
    let peakRow = 0;

    for (let row = 1; row < m; row++) {
      if (mat[peakRow][col] >= mat[row][col]) continue;
      peakRow = row;
    }
    const isGreaterLeft = mat[peakRow][col] > (mat[peakRow][col - 1] ?? -1);
    const isGreaterRight = mat[peakRow][col] > (mat[peakRow][col + 1] ?? -1);

    if (isGreaterLeft && isGreaterRight) return [peakRow, col];
    isGreaterLeft ? (left = col + 1) : (right = col - 1);
  }
  return [-1, -1];
};