1901. Find a Peak Element II

Problem Statement

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.

Intuition

Approach:

Similar to Find Peak 1,
Here we find the max element in a particular column

Now this max element we compare with 
Left and Right element , because top and bottom need not be compared as maximum 

Now based on left and right, change the low and high pointers

Links

https://leetcode.com/problems/find-a-peak-element-ii/description/

Video Links

https://www.youtube.com/watch?v=nGGp5XBzC4g&ab_channel=takeUforward

Approach 1:

N*M*4

C++

class Solution {
public:
    bool check(int nrow, int ncol, int m, int n){
        return nrow<m and nrow>=0 and ncol<n and ncol>=0;
    }

    vector<int> findPeakGrid(vector<vector<int>>& arr) {
        int m=arr.size(), n=arr[0].size();
        int drow[] = {-1,1,0,0};
        int dcol[] = {0,0,1,-1};
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int num = arr[i][j];
                bool flag = true;
                for(int k=0; k<4; k++){
                    int nrow = drow[k] + i;
                    int ncol = dcol[k] + j;

                    if(check(nrow, ncol, m, n) and num<arr[nrow][ncol]){
                        flag = false;
                        break;
                    }   
                }

                if(flag == true)
                    return {i,j};
            }
        }

        return {-1,-1};
    }
};

Approach 2:

NlogM

C++

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        int low = 0, high = m-1;
        while(low <= high){
            int maxRow = 0;
            int midCol = (low+high) >> 1;
            for(int row=0; row<n; row++){
                if(mat[row][midCol] > mat[maxRow][midCol]){
                    maxRow = row;
                }
            }
            int currElement =  mat[maxRow][midCol];
            int leftElement = midCol == 0 ? -1 : mat[maxRow][midCol-1];
            int rightElement = midCol == m-1 ? -1 : mat[maxRow][midCol+1];
            
            if(currElement > leftElement && currElement > rightElement)
                return {maxRow, midCol};
            else if(currElement < leftElement)
                high = midCol - 1;
            else
                low = midCol + 1;
            
        }
        return {-1, -1};
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems