# Find a Peak Element II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-a-peak-element-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-a-peak-element-ii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Matrix
**Companies:** [Zeta](https://scaleengineer.com/companies/zeta)
---
## Problem
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:**

![](https://assets.glich.co/dsa/find-a-peak-element-ii/image0.png)

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

**![](https://assets.glich.co/dsa/find-a-peak-element-ii/image1.png)**

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

# Approaches
## Brute Force Iteration
This approach involves iterating through every cell of the matrix and checking if it's a peak element. A cell is a peak if it is strictly greater than all its four adjacent neighbors (top, bottom, left, and right).
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. In the worst case, we might have to scan the entire matrix. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large matrices and does not meet the time complexity requirement of the problem, which is O(m log(n)) or O(n log(m)).
### Explanation
The algorithm iterates through each cell `(i, j)` from `(0, 0)` to `(m-1, n-1)`. For each cell `mat[i][j]`, we compare its value with its four neighbors. The neighbors are `mat[i-1][j]` (top), `mat[i+1][j]` (bottom), `mat[i][j-1]` (left), and `mat[i][j+1]` (right). We must handle boundary conditions. The problem simplifies this by stating the matrix is surrounded by an outer perimeter with the value -1. So, if a neighbor is outside the matrix bounds, its value is considered -1. If `mat[i][j]` is strictly greater than all its existing neighbors, it is a peak, and we return its coordinates `[i, j]`. Since the problem guarantees that a peak always exists, this method will eventually find and return one.

```java
class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int currentVal = mat[i][j];
                int top = (i > 0) ? mat[i - 1][j] : -1;
                int bottom = (i < m - 1) ? mat[i + 1][j] : -1;
                int left = (j > 0) ? mat[i][j - 1] : -1;
                int right = (j < n - 1) ? mat[i][j + 1] : -1;

                if (currentVal > top && currentVal > bottom && currentVal > left && currentVal > right) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1}; // Should not be reached as per problem statement
    }
}
```
### Algorithm
- Iterate through each row `i` from `0` to `m-1`.
- Inside the row loop, iterate through each column `j` from `0` to `n-1`.
- For the current cell `mat[i][j]`, get the values of its four neighbors, treating out-of-bounds neighbors as -1.
- Check if `mat[i][j]` is strictly greater than all four neighbors.
- If it is, return the coordinates `[i, j]`.

## Optimized Approach with Binary Search
This approach uses a divide-and-conquer strategy similar to binary search to find a peak in logarithmic time with respect to one dimension. We can apply binary search on the columns of the matrix. In each step, we reduce the search space (the set of columns) by half.
**Time:** O(m log n). The binary search on `n` columns takes `log n` steps. In each step, we find the maximum in a column, which takes O(m) time. Alternatively, one could binary search on rows for an O(n log m) solution. · **Space:** O(1), as we only use a constant amount of extra space.
**Pros:** Highly efficient and meets the problem's time complexity constraints.; Guaranteed to find a peak due to the greedy ascent property.
**Cons:** Slightly more complex to understand and implement compared to the brute-force approach.
### Explanation
The core idea is to eliminate half of the columns in each step. We start with a search space covering all columns, from `0` to `n-1`. In each iteration of the binary search, we pick the middle column, `midCol`. We then find the row index `maxRow` of the global maximum element in this `midCol`. This takes O(m) time. Now, we consider the element `mat[maxRow][midCol]`. By its definition, it's already greater than its top and bottom neighbors (or they don't exist). We only need to check its left and right neighbors: `mat[maxRow][midCol - 1]` and `mat[maxRow][midCol + 1]`. If `mat[maxRow][midCol]` is greater than both its left and right neighbors, we have found a 2D peak. We can return `[maxRow, midCol]`. If the left neighbor `mat[maxRow][midCol - 1]` is greater, it implies that there must be a peak in the left half of the matrix (columns `0` to `midCol - 1`). This is because we can follow a path of increasing values starting from `mat[maxRow][midCol]` into the left subgrid, and this path must end at a peak. So, we update our search space to the left half. Similarly, if the right neighbor `mat[maxRow][midCol + 1]` is greater, we update our search space to the right half (columns `midCol + 1` to `n-1`). We repeat this process until a peak is found.

```java
class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int lowCol = 0;
        int highCol = n - 1;

        while (lowCol <= highCol) {
            int midCol = lowCol + (highCol - lowCol) / 2;
            
            // Find the row with the maximum element in the middle column
            int maxRow = 0;
            for (int i = 1; i < m; i++) {
                if (mat[i][midCol] > mat[maxRow][midCol]) {
                    maxRow = i;
                }
            }

            int currentVal = mat[maxRow][midCol];
            int leftVal = (midCol > 0) ? mat[maxRow][midCol - 1] : -1;
            int rightVal = (midCol < n - 1) ? mat[maxRow][midCol + 1] : -1;

            if (currentVal > leftVal && currentVal > rightVal) {
                // This is a peak because it's the max in its column (so > top/bottom)
                // and we've checked it's > left/right.
                return new int[]{maxRow, midCol};
            } else if (currentVal < leftVal) {
                // Peak is in the left half
                highCol = midCol - 1;
            } else { // currentVal < rightVal
                // Peak is in the right half
                lowCol = midCol + 1;
            }
        }
        return new int[]{-1, -1}; // Should not be reached
    }
}
```
### Algorithm
- Initialize `lowCol = 0` and `highCol = n - 1` to define the search space for columns.
- While `lowCol <= highCol`:
  - Calculate `midCol = lowCol + (highCol - lowCol) / 2`.
  - Find the maximum element in `midCol`. Let its row index be `maxRow`.
  - Compare `mat[maxRow][midCol]` with its left and right neighbors.
  - If `mat[maxRow][midCol]` is greater than both, it's a peak. Return `[maxRow, midCol]`.
  - If the left neighbor is greater, a peak must exist on the left side. Update `highCol = midCol - 1`.
  - Otherwise (the right neighbor is greater), a peak must exist on the right side. Update `lowCol = midCol + 1`.

# Solutions
### Java

```java
class Solution { public int [] findPeakGrid ( int [][] mat ) { int l = 0 , r = mat . length - 1 ; int n = mat [ 0 ]. length ; while ( l < r ) { int mid = ( l + r ) >> 1 ; int j = maxPos ( mat [ mid ]); if ( mat [ mid ][ j ] > mat [ mid + 1 ][ j ]) { r = mid ; } else { l = mid + 1 ; } } return new int [] { l , maxPos ( mat [ l ])}; } private int maxPos ( int [] arr ) { int j = 0 ; for ( int i = 1 ; i < arr . length ; ++ i ) { if ( arr [ j ] < arr [ i ]) { j = i ; } } return j ; } }
```

### CPP

```cpp
class Solution { public: vector < int > findPeakGrid ( vector < vector < int >>& mat ) { int l = 0 , r = mat . size () - 1 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; int j = distance ( mat [ mid ]. begin (), max_element ( mat [ mid ]. begin (), mat [ mid ]. end ())); if ( mat [ mid ][ j ] > mat [ mid + 1 ][ j ]) { r = mid ; } else { l = mid + 1 ; } } int j = distance ( mat [ l ]. begin (), max_element ( mat [ l ]. begin (), mat [ l ]. end ())); return { l , j }; } };
```

### Python

```python
class Solution : def findPeakGrid ( self , mat : List [ List [ int ]]) -> List [ int ]: l , r = 0 , len ( mat ) - 1 while l < r : mid = ( l + r ) >> 1 j = mat [ mid ]. index ( max ( mat [ mid ])) if mat [ mid ][ j ] > mat [ mid + 1 ][ j ]: r = mid else : l = mid + 1 return [ l , mat [ l ]. index ( max ( mat [ l ]))]
```