Given a 0-indexed M x N matrix mat, find any peak element and return its position as [row, col]. A cell is called a peak if it is strictly greater than its adjacent neighbors on the left, right, top, and bottom. The matrix is surrounded by a border of -1, and no two adjacent cells are equal.
In simple words, find any cell that is bigger than every valid up, down, left, and right neighbor.
Example 1
Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: The element 4 is located at row 0 and column 1. It is strictly greater than its neighbors 1, 3, and the outer perimeter of -1. Returning [0,1] is correct.
Example 2
Input: mat = [[40,20,15],[21,30,14],[7,16,32]]
Output: [1,1]
Explanation: Both [0,0] and [1,1] are peaks satisfies the conditions of peak element, we can return any one of these two.
Brute Force Approach
The most direct idea is to check every cell and test whether it is greater than all four neighbors. If a cell passes all those checks, that cell is a peak. This is the easiest way to understand the problem because it follows the definition exactly, even though it does not use the structure needed for the expected faster solution.
Algorithm
First, check every cell one by one because a peak can appear anywhere in the grid.
For each cell, read its four neighbors carefully. If a neighbor goes outside the matrix, treat that side as
-1because the problem defines an outside boundary.Compare the current cell with left, right, top, and bottom because a peak must be strictly greater than all four directions.
If the current cell is greater than every valid neighbor, return its position immediately because a valid peak has been found.
If the full matrix is scanned and no cell is returned, give
[-1, -1]. This should not happen for valid problem constraints, but it keeps the code complete.
Dry Run
Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the position of any valid peak element. */ vector<int> findPeakGrid(vector<vector<int>>& mat) { int rows = (int)mat.size(); int cols = (int)mat[0].size(); // Traverse each cell in the grid for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { // Initialize top neighbor; defaults to -1 if out of boundary int up = -1; if (i > 0) { // Current cell is not in the top row, so fetch the upper neighbor up = mat[i - 1][j]; } // Initialize bottom neighbor; defaults to -1 if out of boundary int down = -1; if (i + 1 < rows) { // Current cell is not in the bottom row, so fetch the lower neighbor down = mat[i + 1][j]; } // Initialize left neighbor; defaults to -1 if out of boundary int left = -1; if (j > 0) { // Current cell is not in the leftmost column, so fetch the left neighbor left = mat[i][j - 1]; } // Initialize right neighbor; defaults to -1 if out of boundary int right = -1; if (j + 1 < cols) { // Current cell is not in the rightmost column, so fetch the right neighbor right = mat[i][j + 1]; } // Check if current cell is strictly greater than all valid neighbors if (mat[i][j] > up && mat[i][j] > down && mat[i][j] > left && mat[i][j] > right) { // Found a valid peak, return its coordinates immediately return {i, j}; } } } // Return {-1, -1} if no peak element is found return {-1, -1}; }};// Driver code startsint main() { vector<vector<int>> mat = { {10, 20, 15}, {21, 30, 14}, {7, 16, 32} }; Solution obj; vector<int> answer = obj.findPeakGrid(mat); cout << answer[0] << " " << answer[1] << endl; return 0;}Complexity Analysis
Time Complexity: O(M x N), M is the number of rows and N is the number of columns, because every cell may need to be checked once.
Space Complexity: O(1), because constant space is used.
Optimal Approach
The most important observation is about the maximum element in a chosen middle row. Suppose the middle row is picked, and the biggest value in that row is at column col.
Now a very useful thing happens:
The left neighbor cannot be bigger, because this cell is already the maximum in its row.
The right neighbor also cannot be bigger for the same reason.
So for this chosen cell, the only remaining directions that can possibly beat it are up or down. That reduces a 2D decision into a much simpler vertical decision.
If the cell is greater than the element just below it, then a peak must exist in the current row or somewhere above it.If the cell is smaller than the element below it, then a peak must exist somewhere below. This is why binary search becomes possible. Each comparison tells which half of the rows can still contain a peak.
Algorithm
Keep two pointers,
low = 0andhigh = rows - 1, because the peak can be in any row at the beginning.Pick the middle row using
mid = low + (high - low) / 2. This splits the remaining search space into two halves.Find the column index of the maximum element in the middle row. This step is crucial because once the largest element of that row is chosen, left and right neighbors can no longer be larger than it.
Compare that maximum element with the element directly below it, if a lower row exists.
If the middle-row maximum is greater than the value below it, move
hightomid. This is done because the downward direction is not better, so a peak must exist in the current half including the middle row.Otherwise, move
lowtomid + 1. This is done because a larger value exists below, so a peak must exist somewhere in the lower half.Keep repeating until
lowandhighmeet. At that point, one row is left as the answer row.Find the maximum element in that final row again and return its position. That cell works as a peak because the search process already guaranteed that no better vertical direction remains, and it is also the largest in its row.
Key Points
This solution binary-searches rows, but binary-searching columns is also possible.
The trick is not just picking the middle row. The real trick is picking the maximum value inside that row.
The condition
no two adjacent cells are equalhelps keep the direction decision clean.
Dry Run
Find Peak Element 2 Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the position of any valid peak element. */ vector<int> findPeakGrid(vector<vector<int>>& mat) { int rows = (int)mat.size(); int cols = (int)mat[0].size(); int low = 0; int high = rows - 1; while (low < high) { // Pick the middle row of the current search space. int mid = low + (high - low) / 2; // This stores the column of the largest value in the middle row. int bestCol = 0; for (int col = 1; col < cols; col++) { // Keep the column where the current row has its maximum value. if (mat[mid][col] > mat[mid][bestCol]) { bestCol = col; } } // Move upward if the current row already beats the row below here. if (mat[mid][bestCol] > mat[mid + 1][bestCol]) { high = mid; } else { // Move downward because a larger value exists below in this column. low = mid + 1; } } // Find the largest element again in the final answer row. int bestCol = 0; for (int col = 1; col < cols; col++) { // Keep the column where the final row has its maximum value. if (mat[low][col] > mat[low][bestCol]) { bestCol = col; } } return {low, bestCol}; }};// Driver code startsint main() { vector<vector<int>> mat = { {10, 20, 15}, {21, 30, 14}, {7, 16, 32} }; Solution obj; vector<int> answer = obj.findPeakGrid(mat); cout << answer[0] << " " << answer[1] << endl; return 0;}Complexity Analysis
Time Complexity: O(N x log M), M is the number of rows and N is the number of columns, N is for the inner for-loop to search the max-element in the row. And log M is because Binary search on the rows.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
Because once the maximum of that row is chosen, the left and right neighbors are automatically not larger. That leaves only the vertical direction to decide the search.
Be the first to add a comment.