In this guide, you will get 1901. Find a Peak Element II LeetCode Solution with the best time and space complexity. The solution to Find a Peak Element II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
1901. Find a Peak Element II LeetCode Solution in C++
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int l = 0;
int r = mat.size() - 1;
while (l < r) {
const int m = (l + r) / 2;
if (ranges::max(mat[m]) >= ranges::max(mat[m + 1]))
r = m;
else
l = m + 1;
}
return {l, getMaxIndex(mat[l])};
}
private:
int getMaxIndex(const vector<int>& arr) {
pair<int, int> res{0, arr[0]};
for (int i = 1; i < arr.size(); ++i)
if (arr[i] > res.second)
res = {i, arr[i]};
return res.first;
}
}; /* code provided by PROGIEZ */
1901. Find a Peak Element II LeetCode Solution in Java
class Solution {
public int[] findPeakGrid(int[][] mat) {
int l = 0;
int r = mat.length - 1;
while (l < r) {
final int m = (l + r) / 2;
if (Arrays.stream(mat[m]).max().getAsInt() >= Arrays.stream(mat[m + 1]).max().getAsInt())
r = m;
else
l = m + 1;
}
return new int[] {l, getMaxIndex(mat[l])};
}
private int getMaxIndex(int[] arr) {
int[] res = {0, arr[0]};
for (int i = 1; i < arr.length; ++i)
if (arr[i] > res[1])
res = new int[] {i, arr[i]};
return res[0];
}
} // code provided by PROGIEZ
1901. Find a Peak Element II LeetCode Solution in Python
class Solution:
def findPeakGrid(self, mat: list[list[int]]) -> list[int]:
l = 0
r = len(mat) - 1
while l < r:
m = (l + r) // 2
if max(mat[m]) >= max(mat[m + 1]):
r = m
else:
l = m + 1
return [l, mat[l].index(max(mat[l]))] # code by PROGIEZ
