Find a Peak Element II solution and explanation
Google
7 more videos on this problem
Leetcode 1901 Find a Peak Element II - Implementation using a flavor of binary searchAlgorithmicIQ · 19:18 · 12K views
1901. Find a Peak Element II Explained | Find a peak element in a 2D arrayRay Li CS · 13:17 · 3K views
Leetcode 1901: Find a Peak Element II | Binary Search | Intuition and ApproachCode Concepts with Animesh · 22:10 · 3K views
Google - Find a Peak Element II | 1901 Find a Peak Element II LeetCode | CoderNightCoderNight · 6:28 · 3K views
Find a peak element II | Leetcode | Medium | JavaAlgorithmHQ · 7:36 · 3K views
Leetcode Algorithm III day 1 | 1901. Find a Peak Element II 中文Code Learning · 5:33 · 971 views
Find Peak Element II - Leetcode 1901 | Divide & Conquer SolutionWeb Coder Abhishek · 8:41 · 278 views
LeetCode 1901: Find a Peak Element IIAlitaCode · 29:54 · 10 views
The 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:
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.lengthn == mat[i].length1 <= m, n <= 5001 <= mat[i][j] <= 105- No two adjacent cells are equal.
Approach overview
Problem Overview: You are given an array in the form of a 2D grid. A peak element is a cell strictly greater than its up, down, left, and right neighbors. The task is to return the position of any such peak in the matrix.
Approach 1: Brute Force Scan (O(m * n) time, O(1) space)
The most direct solution checks every cell in the grid. For each position (r, c), compare the value with its four neighbors if they exist. If the current cell is greater than all valid neighbors, you found a peak and can return immediately. This approach uses simple iteration over the matrix and constant extra space. It works for all cases but becomes inefficient when the matrix is large because every element may need to be inspected.
Approach 2: Binary Search on Columns (O(m log n) time, O(1) space)
This approach applies binary search across columns instead of scanning the whole grid. Pick the middle column and find the row containing the maximum value in that column by iterating through all rows. Compare this value with its left and right neighbors. If it is greater than both, you found a peak. If the right neighbor is larger, move the search to the right half of the matrix; if the left neighbor is larger, move left. Each step halves the search space across columns while scanning only one column. The key insight is that moving toward the larger neighbor guarantees a peak exists in that direction.
Approach 3: Binary Search on Rows (O(n log m) time, O(1) space)
This variation performs binary search across rows instead of columns. Select the middle row, then find the column containing the maximum value within that row. Compare this value with the cells above and below it. If it is greater than both vertical neighbors, it forms a peak. Otherwise move the search upward or downward depending on which neighbor is larger. This method mirrors the column-based strategy and works well when the number of columns is significantly larger than rows.
Recommended for interviews: Binary search on columns is the most common solution interviewers expect for problems involving a matrix peak search. It reduces the search space logarithmically while scanning only one column each step, giving O(m log n) time. Starting with a brute force explanation shows you understand the definition of a peak, but transitioning to binary search demonstrates algorithmic optimization and familiarity with 2D search patterns.
Approach 1: Binary Search on Columns
Perform a binary search on matrix columns to find a peak element. At each step, check the maximum element in the middle column, and use it to decide the next direction for the binary search. The search compares the maximum of the middle column with its neighbors in the previous and next columns to direct its search toward the greater neighbor, as this increases the chance of finding a peak.
class Solution:
def findPeakGrid(self, mat):
left, right = 0, len(mat[0]) - 1
while left <= right:
mid = left + (right - left) // 2
max_row = max(range(len(mat)), key=lambda x: mat[x][mid])
if (mid == 0 or mat[max_row][mid] > mat[max_row][mid - 1]) and \
(mid == len(mat[0]) - 1 or mat[max_row][mid] > mat[max_row][mid + 1]):
return [max_row, mid]
elif mid > 0 and mat[max_row][mid - 1] > mat[max_row][mid]:
right = mid - 1
else:
left = mid + 1
return Noneclass Solution {
public int[] findPeakGrid(int[][] mat) {
int left = 0, right = mat[0].length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int maxRow = 0;
for (int i = 0; i < mat.length; i++) {
if (mat[i][mid] > mat[maxRow][mid]) {
maxRow = i;
}
}
if ((mid == 0 || mat[maxRow][mid] > mat[maxRow][mid - 1]) &&
(mid == mat[0].length - 1 || mat[maxRow][mid] > mat[maxRow][mid + 1])) {
return new int[]{maxRow, mid};
} else if (mid > 0 && mat[maxRow][mid - 1] > mat[maxRow][mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return new int[]{};
}
}#include <vector>
using namespace std;
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int left = 0, right = mat[0].size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int maxRow = 0;
for (int i = 0; i < mat.size(); ++i) {
if (mat[i][mid] > mat[maxRow][mid]) {
maxRow = i;
}
}
if ((mid == 0 || mat[maxRow][mid] > mat[maxRow][mid - 1]) &&
(mid == mat[0].size() - 1 || mat[maxRow][mid] > mat[maxRow][mid + 1])) {
return {maxRow, mid};
} else if (mid > 0 && mat[maxRow][mid - 1] > mat[maxRow][mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return {};
}var findPeakGrid = function(mat) {
let left = 0, right = mat[0].length - 1;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
let maxRow = 0;
for (let i = 0; i < mat.length; i++) {
if (mat[i][mid] > mat[maxRow][mid]) {
maxRow = i;
}
}
if ((mid === 0 || mat[maxRow][mid] > mat[maxRow][mid - 1]) &&
(mid === mat[0].length - 1 || mat[maxRow][mid] > mat[maxRow][mid + 1])) {
return [maxRow, mid];
} else if (mid > 0 && mat[maxRow][mid - 1] > mat[maxRow][mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return null;
};#include <stdio.h>
int* findPeakGrid(int** mat, int matSize, int* matColSize, int* returnSize) {
int left = 0, right = matColSize[0] - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int maxRow = 0;
for (int i = 0; i < matSize; ++i) {
if (mat[i][mid] > mat[maxRow][mid]) {
maxRow = i;
}
}
if ((mid == 0 || mat[maxRow][mid] > mat[maxRow][mid - 1]) &&
(mid == matColSize[0] - 1 || mat[maxRow][mid] > mat[maxRow][mid + 1])) {
*returnSize = 2;
int* result = (int*)malloc(*returnSize * sizeof(int));
result[0] = maxRow;
result[1] = mid;
return result;
} else if (mid > 0 && mat[maxRow][mid - 1] > mat[maxRow][mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return NULL;
}public class Solution {
public int[] FindPeakGrid(int[][] mat) {
int left = 0, right = mat[0].Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int maxRow = 0;
for (int i = 0; i < mat.Length; i++) {
if (mat[i][mid] > mat[maxRow][mid]) {
maxRow = i;
}
}
if ((mid == 0 || mat[maxRow][mid] > mat[maxRow][mid - 1]) &&
(mid == mat[0].Length - 1 || mat[maxRow][mid] > mat[maxRow][mid + 1])) {
return new int[] { maxRow, mid };
} else if (mid > 0 && mat[maxRow][mid - 1] > mat[maxRow][mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return null;
}
}This Python method leverages binary search on columns, selecting the maximum in the middle column and comparing it against adjacent values to verify if it's a peak, guiding accordingly based on greater neighbors.
Time Complexity: O(m log(n))
Space Complexity: O(1)
Approach 2: Binary Search on Rows
Employ a binary search on rows to locate a peak element. Here, for a given row, determine the maximum element and assess its neighbors in adjacent rows. Adjust the focus of the binary search towards the row containing the greater value to find a peak element efficiently.
class Solution:
def findPeakGrid(self, mat):
top, bottom = 0, len(mat) - 1
while top <= bottom:
mid = top + (bottom - top) // 2
max_col = max(range(len(mat[0])), key=lambda x: mat[mid][x])
if (mid == 0 or mat[mid][max_col] > mat[mid-1][max_col]) and \
(mid == len(mat) - 1 or mat[mid][max_col] > mat[mid+1][max_col]):
return [mid, max_col]
elif mid > 0 and mat[mid-1][max_col] > mat[mid][max_col]:
bottom = mid - 1
else:
top = mid + 1
return Noneclass Solution {
public int[] findPeakGrid(int[][] mat) {
int top = 0, bottom = mat.length - 1;
while (top <= bottom) {
int mid = top + (bottom - top) / 2;
int maxCol = 0;
for (int j = 0; j < mat[0].length; j++) {
if (mat[mid][j] > mat[mid][maxCol]) {
maxCol = j;
}
}
if ((mid == 0 || mat[mid][maxCol] > mat[mid - 1][maxCol]) &&
(mid == mat.length - 1 || mat[mid][maxCol] > mat[mid + 1][maxCol])) {
return new int[]{mid, maxCol};
} else if (mid > 0 && mat[mid - 1][maxCol] > mat[mid][maxCol]) {
bottom = mid - 1;
} else {
top = mid + 1;
}
}
return new int[]{};
}
}#include <vector>
using namespace std;
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int top = 0, bottom = mat.size() - 1;
while (top <= bottom) {
int mid = top + (bottom - top) / 2;
int maxCol = 0;
for (int j = 0; j < mat[0].size(); j++) {
if (mat[mid][j] > mat[mid][maxCol]) {
maxCol = j;
}
}
if ((mid == 0 || mat[mid][maxCol] > mat[mid - 1][maxCol]) &&
(mid == mat.size() - 1 || mat[mid][maxCol] > mat[mid + 1][maxCol])) {
return {mid, maxCol};
} else if (mid > 0 && mat[mid - 1][maxCol] > mat[mid][maxCol]) {
bottom = mid - 1;
} else {
top = mid + 1;
}
}
return {};
}var findPeakGrid = function(mat) {
let top = 0, bottom = mat.length - 1;
while (top <= bottom) {
let mid = Math.floor(top + (bottom - top) / 2);
let maxCol = 0;
for (let j = 0; j < mat[0].length; j++) {
if (mat[mid][j] > mat[mid][maxCol]) {
maxCol = j;
}
}
if ((mid === 0 || mat[mid][maxCol] > mat[mid - 1][maxCol]) &&
(mid === mat.length - 1 || mat[mid][maxCol] > mat[mid + 1][maxCol])) {
return [mid, maxCol];
} else if (mid > 0 && mat[mid - 1][maxCol] > mat[mid][maxCol]) {
bottom = mid - 1;
} else {
top = mid + 1;
}
}
return null;
};#include <stdio.h>
int* findPeakGrid(int** mat, int matSize, int* matColSize, int* returnSize) {
int top = 0, bottom = matSize - 1;
while (top <= bottom) {
int mid = top + (bottom - top) / 2;
int maxCol = 0;
for (int j = 0; j < matColSize[0]; ++j) {
if (mat[mid][j] > mat[mid][maxCol]) {
maxCol = j;
}
}
if ((mid == 0 || mat[mid][maxCol] > mat[mid - 1][maxCol]) &&
(mid == matSize - 1 || mat[mid][maxCol] > mat[mid + 1][maxCol])) {
*returnSize = 2;
int* result = (int*)malloc(*returnSize * sizeof(int));
result[0] = mid;
result[1] = maxCol;
return result;
} else if (mid > 0 && mat[mid - 1][maxCol] > mat[mid][maxCol]) {
bottom = mid - 1;
} else {
top = mid + 1;
}
}
return NULL;
}public class Solution {
public int[] FindPeakGrid(int[][] mat) {
int top = 0, bottom = mat.Length - 1;
while (top <= bottom) {
int mid = top + (bottom - top) / 2;
int maxCol = 0;
for (int j = 0; j < mat[0].Length; j++) {
if (mat[mid][j] > mat[mid][maxCol]) {
maxCol = j;
}
}
if ((mid == 0 || mat[mid][maxCol] > mat[mid - 1][maxCol]) &&
(mid == mat.Length - 1 || mat[mid][maxCol] > mat[mid + 1][maxCol])) {
return new int[] { mid, maxCol };
} else if (mid > 0 && mat[mid - 1][maxCol] > mat[mid][maxCol]) {
bottom = mid - 1;
} else {
top = mid + 1;
}
}
return null;
}
}This Python solution implements binary search over the rows, assessing the highest within the middle row against adjacent rows. It narrows the search scope, steering endeavors towards the greater adjacent value.
Time Complexity: O(n log(m))
Space Complexity: O(1)
Approach 3: Binary Search
Let m and n be the number of rows and columns of the matrix, respectively.
The problem asks us to find a peak, and the time complexity should be O(m times log n) or O(n times log m). Therefore, we can consider using binary search.
We consider the maximum value of the i-th row, and denote its index as j.
If mat[i][j] > mat[i + 1][j], then there must be a peak in the rows [0,..i]. We only need to find the maximum value in these rows. Similarly, if mat[i][j] < mat[i + 1][j], then there must be a peak in the rows [i + 1,..m - 1]. We only need to find the maximum value in these rows.
Why is the above method correct? We can prove it by contradiction.
If mat[i][j] > mat[i + 1][j], suppose there is no peak in the rows [0,..i]. Then mat[i][j] is not a peak. Since mat[i][j] is the maximum value of the i-th row, and mat[i][j] > mat[i + 1][j], then mat[i][j] < mat[i - 1][j]. We continue to consider from the (i - 1)-th row upwards, and the maximum value of each row is less than the maximum value of the previous row. When we traverse to i = 0, since all elements in the matrix are positive integers, and the values of the cells around the matrix are -1. Therefore, at the 0-th row, its maximum value is greater than all its adjacent elements, so the maximum value of the 0-th row is a peak, which contradicts the assumption. Therefore, there must be a peak in the rows [0,..i].
For the case where mat[i][j] < mat[i + 1][j], we can prove in a similar way that there must be a peak in the rows [i + 1,..m - 1].
Therefore, we can use binary search to find the peak.
We perform binary search on the rows of the matrix, initially with the search boundaries l = 0, r = m - 1. Each time, we find the middle row mid and find the index j of the maximum value of this row. If mat[mid][j] > mat[mid + 1][j], then we search for the peak in the rows [0,..mid], i.e., update r = mid. Otherwise, we search for the peak in the rows [mid + 1,..m - 1], i.e., update l = mid + 1. When l = r, we find the position [l, j_l] of the peak, where j_l is the index of the maximum value of the l-th row.
The time complexity is O(n times log m), where m and n are the number of rows and columns of the matrix, respectively. The time complexity of binary search is O(log m), and each time we perform binary search, we need to traverse all elements of the mid-th row, with a time complexity of O(n). The space complexity is O(1).
function findPeakGrid(mat: number[][]): number[] {
let [l, r] = [0, mat.length - 1];
while (l < r) {
const mid = (l + r) >> 1;
const j = mat[mid].indexOf(Math.max(...mat[mid]));
if (mat[mid][j] > mat[mid + 1][j]) {
r = mid;
} else {
l = mid + 1;
}
}
return [l, mat[l].indexOf(Math.max(...mat[l]))];
}func findPeakGrid(mat [][]int) []int {
maxPos := func(arr []int) int {
j := 0
for i := 1; i < len(arr); i++ {
if arr[i] > arr[j] {
j = i
}
}
return j
}
l, r := 0, len(mat)-1
for l < r {
mid := (l + r) >> 1
j := maxPos(mat[mid])
if mat[mid][j] > mat[mid+1][j] {
r = mid
} else {
l = mid + 1
}
}
return []int{l, maxPos(mat[l])}
}impl Solution {
pub fn find_peak_grid(mat: Vec<Vec<i32>>) -> Vec<i32> {
let mut l: usize = 0;
let mut r: usize = mat.len() - 1;
while l < r {
let mid: usize = (l + r) >> 1;
let j: usize = mat[mid]
.iter()
.position(|&x| x == *mat[mid].iter().max().unwrap())
.unwrap();
if mat[mid][j] > mat[mid + 1][j] {
r = mid;
} else {
l = mid + 1;
}
}
let j: usize = mat[l]
.iter()
.position(|&x| x == *mat[l].iter().max().unwrap())
.unwrap();
vec![l as i32, j as i32]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search on Columns | Time Complexity: O(m log(n)) |
| Binary Search on Rows | Time Complexity: O(n log(m)) |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(m * n) | O(1) | Good for understanding the peak definition or when matrix size is small |
| Binary Search on Columns | O(m log n) | O(1) | Best general solution for large matrices; reduces search space by half each step |
| Binary Search on Rows | O(n log m) | O(1) | Useful when rows are fewer than columns or when row scanning is cheaper |
Frequently asked questions
Is Find a Peak Element II easy or hard?
Find a Peak Element II is considered a medium difficulty problem. The challenge is recognizing that binary search can be applied to a matrix by selecting a row or column maximum and moving toward the larger neighbor.
Find a Peak Element II Python or Java solution?
Most implementations follow the binary search on columns approach. The algorithm repeatedly scans the middle column for its maximum element and adjusts the search boundaries. This logic translates directly into Python, Java, C++, C#, and JavaScript.
How to solve Find a Peak Element II in O(m log n)?
Use binary search over columns. At each step, select the middle column, find the row with the maximum value in that column, and compare it with its left and right neighbors. Move the search toward the larger neighbor until a peak is found.
What is the best approach for Find a Peak Element II?
Binary search on columns is the most widely used approach. It finds the maximum element in the middle column and compares it with adjacent columns to decide the search direction. This reduces the search space logarithmically and runs in O(m log n) time with O(1) space.
What data structure is used in Find a Peak Element II?
The problem uses a 2D matrix represented as a grid or 2D array. The key technique applied is binary search on rows or columns rather than additional data structures.
What is the time complexity of Find a Peak Element II?
The optimal solution runs in O(m log n) time using binary search on columns, where m is the number of rows and n is the number of columns. Each step scans one column to find its maximum, and the binary search halves the column range.
Is Find a Peak Element II asked at Google, Amazon, or Meta?
Peak element and matrix binary search problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants test the ability to apply binary search in multidimensional data structures.