1901

1901. Find a Peak Element II (Medium)

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.

Companies:
Microsoft

Related Topics:
Array, Binary Search, Divide and Conquer, Matrix

Similar Questions:

• Find Peak Element (Medium)

Solution 1. Binary Search (L < R)

// OJ: https://leetcode.com/problems/find-a-peak-element-ii/
// Author: github.com/lzl124631x
// Time: O(NlogM)
// Space: O(1)
class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), L = 0, R = M - 1;
        while (L < R) {
            int mid = (L + R + 1) / 2;
            int left = mid - 1 >= 0 ? *max_element(begin(A[mid - 1]), end(A[mid - 1])) : -1;
            int cur = *max_element(begin(A[mid]), end(A[mid]));
            if (cur > left) L = mid;
            else R = mid - 1;
        }
        return { L, int(max_element(begin(A[L]), end(A[L])) - begin(A[L])) };
    }
};