> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-on-2d-arrays/1901.-find-a-peak-element-ii.md).

# 1901. Find a Peak Element II

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/06/08/1.png)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/06/07/3.png)

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

&#x20;

**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
```

{% code title="C++" lineNumbers="true" %}

```cpp
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};
    }
};
```

{% endcode %}

### Approach 2:

```
NlogM
```

{% code title="C++" lineNumbers="true" %}

```cpp
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};
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###