1901. Find a Peak Element II

Problem Description

Given a 2D grid represented as a 0-indexed m x n matrix mat, where each element mat[i][j] is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom, the goal is to find any peak element in the grid. A peak element is surrounded by an outer perimeter with the value -1 in each cell. The task is to return the length 2 array [i, j] for any peak element mat[i][j], and the algorithm must have a time complexity of O(m log(n)) or O(n log(m)).

Example:

Consider the following input matrix mat:

1
2
3mat = [
4    [1, 4],
5    [3, 2]
6]

The peak element in this matrix is mat[0][1] with the value 4. Hence, the correct output would be [0, 1].

Approach

The solution is based on a binary search algorithm where we perform the search across rows. We first find the middle row and compare the maximum element of the middle row with the maximum element of the adjacent row. We then adjust the search space based on the comparison result and continue the search until we find the row containing the peak element. Finally, we find the column index of the peak element in that row and return the coordinates as a pair [i, j].

Example

Let's walk through an example to understand how the algorithm works:

Suppose we have the following grid:

1
2
3mat = [
4    [1, 2, 3],
5    [4, 5, 1],
6    [5, 4, 6]
7]

1. First, we initialize the left (l) and right (r) boundaries as l = 0 and r = mat.size() - 1 (which is 2).

2. Now we start a while loop until l < r.

3. In each iteration, we find the middle row m as (l + r) / 2.

   • For the first iteration, m = (0 + 2) / 2 = 1.

4. We compare the maximum element of row m with the maximum element of row m + 1.

   • For the first iteration, the maximum element of row 1 is 5 and the maximum element of row 2 is 6. Since 5 < 6, we update l to m + 1 (which is 2).

5. The loop continues until l >= r. When this happens, we found the row containing the peak element.

   • In this case, the loop ends when l = 2.

6. To get the column index of the peak element, we call the helper function getMaxIndex() with the row containing the peak element.

   • Here, we pass row [5, 4, 6] to the function, which returns the index 2.

7. The algorithm returns [2, 2], which is the correct location of the peak element mat[2][2] with the value 6.

Solution using C++

1
2cpp
3#include <vector>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 public:
10  vector<int> findPeakGrid(vector<vector<int>>& mat) {
11    int l = 0;
12    int r = mat.size() - 1;
13
14    while (l < r) {
15      const int m = (l + r) / 2;
16      if (*max_element(begin(mat[m]), end(mat[m])) >=
17          *max_element(begin(mat[m + 1]), end(mat[m + 1])))
18        r = m;
19      else
20        l = m + 1;
21    }
22
23    return {l, getMaxIndex(mat[l])};
24  }
25
26 private:
27  int getMaxIndex(const vector<int>& A) {
28    pair<int, int> res{0, A[0]};
29    for (int i = 1; i < A.size(); ++i)
30      if (A[i] > res.second)
31        res = {i, A[i]};
32    return res.first;
33  }
34};

Solution using Java

1
2java
3import java.util.ArrayList;
4import java.util.Arrays;
5
6class Solution {
7    public int[] findPeakGrid(int[][] mat) {
8        int l = 0;
9        int r = mat.length - 1;
10
11        while (l < r) {
12            int m = (l + r) / 2;
13            if (Arrays.stream(mat[m]).max().getAsInt() >=
14                Arrays.stream(mat[m + 1]).max().getAsInt()) {
15                r = m;
16            } else {
17                l = m + 1;
18            }
19        }
20
21        return new int[]{l, getMaxIndex(mat[l])};
22    }
23
24    private int getMaxIndex(int[] A) {
25        int resIndex = 0;
26        int resValue = A[0];
27        for (int i = 1; i < A.length; ++i) {
28            if (A[i] > resValue) {
29                resIndex = i;
30                resValue = A[i];
31            }
32        }
33
34        return resIndex;
35    }
36}

Solution using Python

1
2python
3from typing import List
4
5class Solution:
6    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
7        l = 0
8        r = len(mat) - 1
9
10        while l < r:
11            m = (l + r) // 2
12            if max(mat[m]) >= max(mat[m + 1]):
13                r = m
14            else:
15                l = m + 1
16
17        return [l, mat[l].index(max(mat[l]))]

Solution using JavaScript

1
2javascript
3/**
4 * @param {number[][]} mat
5 * @return {number[]}
6 */
7var findPeakGrid = function(mat) {
8    let l = 0;
9    let r = mat.length - 1;
10
11    while (l < r) {
12        const m = Math.floor((l + r) / 2);
13        if (Math.max(...mat[m]) >= Math.max(...mat[m + 1])) {
14            r = m;
15        } else {
16            l = m + 1;
17        }
18    }
19
20    return [l, mat[l].indexOf(Math.max(...mat[l]))];
21};

Solution using C#

1
2csharp
3using System;
4using System.Linq;
5
6public class Solution {
7    public int[] FindPeakGrid(int[][] mat) {
8        int l = 0;
9        int r = mat.Length - 1;
10
11        while (l < r) {
12            int m = (l + r) / 2;
13            if (mat[m].Max() >= mat[m + 1].Max()) {
14                r = m;
15            } else {
16                l = m + 1;
17            }
18        }
19
20        return new int[]{l, Array.IndexOf(mat[l], mat[l].Max())};
21    }
22}

By using binary search algorithm based on the rows of the grid, we were able to create solutions to find the peak element in a grid for multiple programming languages including C++, Java, Python, JavaScript, and C#. The time complexities of these solutions are O(m log(n)) or O(n log(m)), which meet the desired criteria.