1901. Find a Peak Element II

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.

• new solution update 2022.05.10

c++

class Solution {
    bool bigger(vector<vector<int>>& mat, int y, int x) {
        int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
        int n = mat.size(), m = mat[0].size();
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if(0 <= ny and ny < n and 0 <= nx and nx < m and mat[ny][nx] >= mat[y][x]) {
                return false;
            }
        }
        return true;
    }
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size(), i = 0;
        while(true) {
            int l = 0, r = m - 1;
            while(l <= r) {
                int mid = l + (r - l) / 2;
                if(mid + 1 < m and mat[i][mid + 1] >= mat[i][mid])
                    l = mid + 1;
                else if(mid - 1 >= 0 and mat[i][mid - 1] >= mat[i][mid])
                    r = mid - 1;
                else if(i + 1 < n and mat[i + 1][mid] >= mat[i][mid])
                    i += 1;
                else if(i - 1 >= 0 and mat[i - 1][mid] >= mat[i][mid])
                    i -= 1;
                else return {i, mid};
            }
        }
        return {};
    }
};

c++

class Solution {
    int getOrDefault(vector<int>& nums, int i, int def = INT_MIN) {
        if(i < 0 or i >= nums.size())
            return def;
        return nums[i];
    }
    int getOrDefault(vector<vector<int>>& mat, int y, int x, int def = INT_MIN) {
        if(0 <= y and y < mat.size()) {
            return mat[y][x];
        }
    return def;
    }
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int l = 0, r = mat[0].size(), y = 0;
        while(true) {
            int m = l + (r - l) / 2;
            int left = getOrDefault(mat[y], m - 1);
            int right = getOrDefault(mat[y], m + 1);
            if(left < mat[y][m] and mat[y][m] > right) {
                int up = getOrDefault(mat, y - 1, m);
                int down = getOrDefault(mat, y + 1, m);
                
                if(up < mat[y][m] and mat[y][m] > down)
                    return {y, m};
                else if(up > down) y--;
                else y++;
                
            } else if (left > right) r = m - 1;
            else l = m + 1;
        }
        return {-1,-1};
    }
};