Find a Peak Element II - Solution & Explanation
Problem Statement
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.
This C implementation uses binary search on columns. It identifies the maximum element in the middle column, then checks its neighbors. If it's a peak, it returns the element's position; otherwise, it moves the search to the direction of the greater neighbor.
Complexity
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.
This C solution uses binary search on rows to locate a peak. It finds the maximal column index in the middle row, evaluates adjacent rows, and uses conditions to identify a peak or refocus the search direction efficiently.
Complexity
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).
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 | — |
Detailed 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 |
Video Solution
Leetcode 1901 Find a Peak Element II - Implementation using a flavor of binary search • AlgorithmicIQ • 12,745 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Find a Peak Element II easy or hard?
Find a Peak Element II Python or Java solution?
How to solve Find a Peak Element II in O(m log n)?
What is the best approach for Find a Peak Element II?
What data structure is used in Find a Peak Element II?
What is the time complexity of Find a Peak Element II?
Is Find a Peak Element II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Find a Peak Element II with our built-in code editor and test cases.
Practice on FleetCode