Find a Peak Element II Solution In C++/Java/Python/JS
Problem Description:
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.
Examples
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.
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] <= 10⁵
- No two adjacent cells are equal.
Given an n×m matrix, we need to find peak element. peak element is in 2d matrix is the index where the value is greater than the values of its four neighbouring elements.
Now that we understand our problem, let's try building our naive solution.
Naive Approach to Find Peak Element in Matrix
Intuition:
We are given a matrix, and to find the peak element, we just need to find a position that satisfies the peak element condition. With this in mind, the first thought that arises is, "Why not check every position in the matrix to see if it is a peak element or not?" This sounds straightforward: start from the first position, check if it meets the peak element condition, and if it does, we have our answer. Hurray!. Otherwise, move to the next position
One thing to notice here is that the matrix is surrounded by -1 which means we just need to check valid neighbors for boundary values. Example. For a value at the top right corner of the matrix just check the peak element condition for the values at positions left and bottom.
Peak Element-II Solution
However, let’s imagine what happens as we go through this process. For each position, we compare the value with its neighbours (top, left, right, and bottom) to determine if it is a peak element. If it isn’t, we move on to the next consecutive position and repeat the check. This brute-force approach guarantees that we will find a peak eventually, but at what cost?
Think about the size of the matrix. If the matrix has n rows and m columns, we end up making n×m comparisons in the worst-case scenario. This is quite intensive, especially for large matrices, where n and m can be very large.
Dry run
Input: mat = [[8,13,4],[23,12,17],[7,16,32]]
Output: [2, 2]
Explanation: Here values at position [1, 0], [0, 1], [2, 2] are all peaks.
Initialization:
- The matrix size n is 3 (number of rows), and mm is 3 (number of columns).
First Outer Loop Iteration (i=0):
- First Inner Loop Iteration (j=0):
- top = -1 (no element above)
- bottom = 23
- left = -1 (no element to the left)
- right = 13
- Condition: top<8 and left<8 and bottom<8 and right<8 is false (since 23 > 8 and 13 > 8).
- Second Inner Loop Iteration (j=1):
- top = -1 (no element above)
- bottom = 12
- left = 8
- right = 4
- Condition: top<13 and left<13 and bottom<13 and right<13 is true.
- Peak found at position: (0,1).
- The function returns the position (0,1) as the peak.
Steps to write code
Step 1: Initialize Dimensions:
- Determine the number of rows m and columns n in the matrix.
Step 2: Outer Loop for Rows:
- Loop through each row index i from 0 to m-1.
Step 3: Inner Loop for Columns:
- Inside the row loop, loop through each column index j from 0 to n-1.
Step 4: Identify Neighbors:
- For each element at position (i, j), identify the values of its top, bottom, left, and right neighbors. Ensure to handle boundary conditions where neighbors might not exist.
Step 5: Peak Check:
- Check if the current element is greater than all its identified neighbors. If true, this element is a peak.
Step 6: Return Peak Position:
- If a peak is found, return the position (i, j).
Step 7: Fallback Return:
- If no peak is found after checking all positions, return {-1, -1} as a fallback.
Peak Element II Solutions
Find-a-peak-element-ii leetcode in c++
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int numRows = mat.size(); // Get the number of rows
int numCols = mat[0].size(); // Get the number of columns
// Loop through each row
for(int row = 0; row < numRows; ++row) {
// Loop through each column
for(int col = 0; col < numCols; ++col) {
// Check the value of the top neighbor, if it exists
int top = row - 1 >= 0 ? mat[row - 1][col] : -1;
// Check the value of the bottom neighbor, if it exists
int bottom = row + 1 < numRows ? mat[row + 1][col] : -1;
// Check the value of the left neighbor, if it exists
int left = col - 1 >= 0 ? mat[row][col - 1] : -1;
// Check the value of the right neighbor, if it exists
int right = col + 1 < numCols ? mat[row][col + 1] : -1;
// If the current element is greater than all its neighbors
if(top < mat[row][col] && left < mat[row][col] && bottom < mat[row][col] && right < mat[row][col]) {
// Return the position of the peak
return {row, col};
}
}
}
// If no peak is found, return {-1, -1}
return {-1, -1};
}
};Find-a-peak-element-ii leetcode in java
class Solution {
public int[] findPeakGrid(int[][] mat) {
int numRows = mat.length; // Get the number of rows
int numCols = mat[0].length; // Get the number of columns
// Loop through each row
for(int row = 0; row < numRows; ++row) {
// Loop through each column
for(int col = 0; col < numCols; ++col) {
// Check the value of the top neighbor, if it exists
int top = row - 1 >= 0 ? mat[row - 1][col] : -1;
// Check the value of the bottom neighbor, if it exists
int bottom = row + 1 < numRows ? mat[row + 1][col] : -1;
// Check the value of the left neighbor, if it exists
int left = col - 1 >= 0 ? mat[row][col - 1] : -1;
// Check the value of the right neighbor, if it exists
int right = col + 1 < numCols ? mat[row][col + 1] : -1;
// If the current element is greater than all its neighbors
if(top < mat[row][col] && left < mat[row][col] && bottom < mat[row][col] && right < mat[row][col]) {
// Return the position of the peak
return new int[]{row, col};
}
}
}
// If no peak is found, return {-1, -1}
return new int[]{-1, -1};
}
}Find-a-peak-element-ii leetcode in python
class Solution:
def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
numRows = len(mat) # Get the number of rows
numCols = len(mat[0]) # Get the number of columns
# Loop through each row
for row in range(numRows):
# Loop through each column
for col in range(numCols):
# Check the value of the top neighbor, if it exists
top = mat[row - 1][col] if row - 1 >= 0 else -1
# Check the value of the bottom neighbor, if it exists
bottom = mat[row + 1][col] if row + 1 < numRows else -1
# Check the value of the left neighbor, if it exists
left = mat[row][col - 1] if col - 1 >= 0 else -1
# Check the value of the right neighbor, if it exists
right = mat[row][col + 1] if col + 1 < numCols else -1
# If the current element is greater than all its neighbors
if top < mat[row][col] and left < mat[row][col] and bottom < mat[row][col] and right < mat[row][col]:
# Return the position of the peak
return [row, col]
# If no peak is found, return [-1, -1]
return [-1, -1]Find-a-peak-element-ii leetcode in javascript
/**
* @param {number[][]} mat
* @return {number[]}
*/
var findPeakGrid = function(mat) {
let numRows = mat.length; // Get the number of rows
let numCols = mat[0].length; // Get the number of columns
// Loop through each row
for (let row = 0; row < numRows; ++row) {
// Loop through each column
for (let col = 0; col < numCols; ++col) {
// Check the value of the top neighbor, if it exists
let top = row - 1 >= 0 ? mat[row - 1][col] : -1;
// Check the value of the bottom neighbor, if it exists
let bottom = row + 1 < numRows ? mat[row + 1][col] : -1;
// Check the value of the left neighbor, if it exists
let left = col - 1 >= 0 ? mat[row][col - 1] : -1;
// Check the value of the right neighbor, if it exists
let right = col + 1 < numCols ? mat[row][col + 1] : -1;
// If the current element is greater than all its neighbors
if (top < mat[row][col] && left < mat[row][col] && bottom < mat[row][col] && right < mat[row][col]) {
// Return the position of the peak
return [row, col];
}
}
}
// If no peak is found, return [-1, -1]
return [-1, -1];
};Complexity Analysis of Peak Element II Solution
Time Complexity: O(n×m)
Initialization:
- Determining the number of rows (m) and columns (n) is O(1) since it involves accessing the matrix dimensions.
Outer Loop for Rows:
- The outer loop runs m times, so its complexity is O(m).
Inner Loop for Columns:
- For each row, the inner loop runs n times, so its complexity is O(n).
Identify Neighbors and Peak Check:
- Checking the neighbors and verifying the peak condition for each element is O(1), but it is done for each element.
Total Complexity:
- Since we have m rows and n columns, and we check each element once, the total complexity is O(n×m).
Space Complexity: O(1)
Auxiliary Space Complexity:
It refers to the space complexity caused by the extra data structures we use to solve the problem.
- Initialization:
- Determining the number of rows m and columns n uses a constant amount of space, i.e., O(1).
- Outer and Inner Loops:
- The loops themselves do not consume additional space beyond the loop variables, which is O(1).
- Neighbor Checks:
- Variables to store the neighbour values (top, bottom, left, right) are also O(1) as they do not depend on the input size.
Thus, the auxiliary space complexity is O(1).
Total Space Complexity:
The total space complexity is the sum of the space required by the input matrix and the auxiliary space.
- Since the matrix itself occupies O(n×m) space and auxiliary space is O(1), the total space complexity is: O(n×m) + O(1) = O(n×m).
Why brute force fails to accept?
With the brute force approach, we evaluated each position in the matrix to determine if it was a peak. Given that there are n×m positions, the overall time complexity is O(n×m).
Considering the constraints, where the maximum value of n and m can be up to 1×10⁵, this implies 1×10⁵ × 1×10⁵=1×10¹⁰, which exceeds the time limit of 1 second. Its because a system can perform maximum 10 operations in a second.
Therefore, we need to optimize our solution.
Efficient Approach to Find Peak Element in Matrix
Intuition:
To optimize our solution, we can't afford to traverse through every position in the matrix. Instead, we need to strategically select a part of the matrix where we are confident that we can find the peak. In this problem, a peak is defined as a value that is greater than its neighbours (top, left, right, bottom). Given that we have n rows and m columns, let's focus on the columns for now.
Imagine we choose any column out of the m columns in the matrix. There are a total of n values in that single column. For the sake of explanation, let's assume that our peak lies in this chosen column.
Out of the four neighbours of any element in this column, we should concentrate on the two vertical neighbours: the top and bottom ones. This is because these neighbours are situated within the same column, while the left and right neighbours are located in adjacent columns.
Peak Element-II Algorithm
We start by considering that the peak element must have a value greater than its neighbours. It would be logical to focus on the greatest value in the selected column. This value will inherently be greater than its top and bottom neighbours. By finding this maximum value, we increase our chances of locating a peak. Makes sense right?
Next, we compare this maximum value with its left and right neighbours. If the maximum value is greater than these neighbours as well, then we have successfully found our peak. However, if it isn't, we can draw certain conclusions which will help reduce our search space.
If the maximum value is not the peak element, meaning that out of the two neighbours (left and right). Then either one out of the left and right adjacent values or both of them will be greater than the maximum value of the selected column, we can use this information to our advantage.
Let's take the case when the maximum value is less than its left neighbour. What does this indicate? It indicates that there's a higher value in the columns to the left. This means the chances of finding a peak are better in that direction.
Since our goal is to find a peak, we can confidently eliminate the right side of the column from our search space because we are sure that there will be at least one peak on the left side of the column.
By focusing our search on the left side, we are following the trail of higher values, leading us closer to a peak. This strategic narrowing down of the search space is based on the logical deduction that peaks are more likely to be found where higher values are present. It’s like following a breadcrumb trail to find the treasure.
Example
Consider the following 2D grid:
2 1 4 3
4 9 8 7
3 2 5 9
First, identify the maximum element in a column. Let's say we pick the column ([4, 8, 5]) and find its maximum value, which is 8 at position (1,2).
Check the left and right neighbours of 8:
- Left neighbor: 9 (greater than 8)
- Right neighbour: 7 (less than 8)
Since the left neighbour is greater than 8, it suggests that a peak might exist on the left side.
We now discard the right half ([3, 7, 9]) and continue searching in the left columns ([1, 6, 2]) and ([2, 4, 3]).
Repeating this process leads us to 9, which is a peak since it is greater than both its adjacent elements (1 and 4).
This way of finding the desired value within the whole search space is called binary search.
To know more about binary search. Refer to the article mentioned below...
To perform a binary search, we initially select the middle column and check the maximum value in that column. Is it a peak element? If it is not, we reduce our search space to the left or right half, depending on whether the greater value lies in the left or right neighbour.
Hence, Applying this same algorithm to find the peak element on this reduced search space will eventually give us any one peak element of the matrix.
In this solution, we applied binary search on the columns and then went through each row, resulting in a time complexity of O(n log(m)), where n is the number of rows and m is the number of columns.
Alternatively, you can switch this approach: perform a binary search on the rows and iterate over the columns to find the maximum value. Both methods work well. The time complexity for this approach would be O(m log(n)).
Let us understand this with a video,
find-a-peak-element-ii-Animation Explaination
Dry run
Input: mat = [[8,13,4],[23,12,17],[7,16,32]]
Output: [2, 2]
Explanation: Here values at position [1, 0], [0, 1], [2, 2] are all peaks.
Initialization:
- n = mat[0].size() = 3 (number of columns)
- m = mat.size() = 3 (number of rows)
- l = 0 (low boundary)
- h = n - 1 = 2 (high boundary)
First Iteration of the While Loop (l = 0, h = 2):
- col = (h + l) / 2 = (2 + 0) / 2 = 1 (middle column)
- Finding the Maximum Element in Column 1:
- Initialize max_row = 0.
- Compare mat[1][1] (value 12) with mat[max_row][1] (value 13): no change.
- Compare mat[2][1] (value 16) with mat[max_row][1] (value 13): update max_row = 2.
- Maximum value in column 1 is mat[2][1] = 16.
- Checking Neighbors of mat[2][1] (value 16):
- left_is_smaller = col - 1 >= l && mat[max_row][col] < mat[max_row][col - 1] (1 - 1 >= 0 && 16 < 7 = false).
- right_is_smaller = col + 1 <= h && mat[max_row][col] < mat[max_row][col + 1] (1 + 1 <= 2 && 16 < 32 = true).
- Decision Making:
- Since left_is_smaller = false and right_is_smaller = true, we set l = col + 1 = 1 + 1 = 2.
Second Iteration of the While Loop (l = 2, h = 2):
- col = (h + l) / 2 = (2 + 2) / 2 = 2 (middle column)
- Finding the Maximum Element in Column 2:
- Initialize max_row = 0.
- Compare mat[1][2] (value 17) with mat[max_row][2] (value 4): update max_row = 1.
- Compare mat[2][2] (value 32) with mat[max_row][2] (value 17): update max_row = 2.
- Maximum value in column 2 is mat[2][2] = 32.
- Checking Neighbors of mat[2][2] (value 32):
- left_is_smaller = col - 1 >= l && mat[max_row][col] < mat[max_row][col - 1] (2 - 1 >= 2 && 32 < 16 = false).
- `right_is_smaller = col + 1 <= h && mat[max_row][col] < mat[max_row][col + 1] (2 + 1 <= 2 && 32 < mat[max_row][col + 1] = false).
- Decision Making:
- Since left_is_smaller = false and right_is_smaller = false, we have found the peak at max_row = 2 and col = 2.
- Return {2, 2}.
Steps to write code
Step 1: Initialize Dimensions:
- Determine the number of rows m and columns n in the matrix.
Step 2: Initialize Boundaries:
- Set low to 0 and high to n-1 (column indices).
Step 3: Main Loop:
- Loop while low is less than or equal to high.
Step 4: Calculate Middle Column (col):
- Calculate the middle column index as (low + high) / 2.
Step 5: Find Maximum in Middle Column (max_row):
- Traverse the middle column to find the maximum value and its corresponding row index.
Step 6: Check Neighbors of Maximum:
- Compare the maximum value with its left and right neighbors to determine if it is a peak.
Step 7: Decision Making:
- If the maximum value is greater than both neighbors (if they exist), return the position as the peak.
- If the left neighbor is greater, adjust high to mid_col - 1.
- If the right neighbor is greater, adjust low to mid_col + 1.
Step 8: Return Peak Position:
- If a peak is found, return the position (max_row, col).
Step 9: Fallback Return:
- If no peak is found after narrowing down the search space, return {-1, -1} as a fallback.
Peak Element II leetcode Solutions
Find-a-peak-element-ii leetcode in C++
class Solution {
public:
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int numRows = mat.size(); // Get the number of rows
int numCols = mat[0].size(); // Get the number of columns
int low = 0, high = numCols - 1; // Initialize low and high pointers
while (low <= high) {
int mid_col = (low + high) / 2; // Find the middle column index
// Find the row with the maximum value in the middle column
int max_row = 0;
for (int i = 0; i < numRows; ++i) {
if (mat[i][mid_col] > mat[max_row][mid_col]) {
max_row = i;
}
}
// Check if the left neighbor is greater, if it exists
bool left_is_bigger = mid_col - 1 >= low && mat[max_row][mid_col] < mat[max_row][mid_col - 1];
// Check if the right neighbor is greater, if it exists
bool right_is_bigger = mid_col + 1 <= high && mat[max_row][mid_col] < mat[max_row][mid_col + 1];
// If the maximum value is greater than both neighbors, return it as the peak
if (!left_is_bigger && !right_is_bigger) {
return {max_row, mid_col};
}
// If the left neighbor is greater, search in the left half
else if (left_is_bigger) {
high = mid_col - 1;
}
// If the right neighbor is greater, search in the right half
else {
low = mid_col + 1;
}
}
// If no peak is found, return {-1, -1}
return {-1, -1};
}
};Find-a-peak-element-ii leetcode in java
class Solution {
public int[] findPeakGrid(int[][] mat) {
int numRows = mat.length; // Get the number of rows
int numCols = mat[0].length; // Get the number of columns
int low = 0, high = numCols - 1; // Initialize low and high pointers
while (low <= high) {
int mid_col = (low + high) / 2; // Find the middle column index
// Find the row with the maximum value in the middle column
int max_row = 0;
for (int i = 0; i < numRows; ++i) {
if (mat[i][mid_col] > mat[max_row][mid_col]) {
max_row = i;
}
}
// Check if the left neighbor is greater, if it exists
boolean left_is_bigger = mid_col - 1 >= low && mat[max_row][mid_col] < mat[max_row][mid_col - 1];
// Check if the right neighbor is greater, if it exists
boolean right_is_bigger = mid_col + 1 <= high && mat[max_row][mid_col] < mat[max_row][mid_col + 1];
// If the maximum value is greater than both neighbors, return it as the peak
if (!left_is_bigger && !right_is_bigger) {
return new int[]{max_row, mid_col};
}
// If the left neighbor is greater, search in the left half
else if (left_is_bigger) {
high = mid_col - 1;
}
// If the right neighbor is greater, search in the right half
else {
low = mid_col + 1;
}
}
// If no peak is found, return {-1, -1}
return new int[]{-1, -1};
}
}Find-a-peak-element-ii leetcode in python
class Solution:
def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
numRows = len(mat) # Get the number of rows
numCols = len(mat[0]) # Get the number of columns
low, high = 0, numCols - 1 # Initialize low and high pointers
while low <= high:
mid_col = (low + high) // 2 # Find the middle column index
# Find the row with the maximum value in the middle column
max_row = 0
for i in range(numRows):
if mat[i][mid_col] > mat[max_row][mid_col]:
max_row = i
# Check if the left neighbor is greater, if it exists
left_is_bigger = mid_col - 1 >= low and mat[max_row][mid_col] < mat[max_row][mid_col - 1]
# Check if the right neighbor is greater, if it exists
right_is_bigger = mid_col + 1 <= high and mat[max_row][mid_col] < mat[max_row][mid_col + 1]
# If the maximum value is greater than both neighbors, return it as the peak
if not left_is_bigger and not right_is_bigger:
return [max_row, mid_col]
# If the left neighbor is greater, search in the left half
elif left_is_bigger:
high = mid_col - 1
# If the right neighbor is greater, search in the right half
else:
low = mid_col + 1
# If no peak is found, return [-1, -1]
return [-1, -1]Find-a-peak-element-ii leetcode in javascript
/**
* @param {number[][]} mat
* @return {number[]}
*/
var findPeakGrid = function(mat) {
let numRows = mat.length; // Get the number of rows
let numCols = mat[0].length; // Get the number of columns
let low = 0, high = numCols - 1; // Initialize low and high pointers
while (low <= high) {
let mid_col = Math.floor((low + high) / 2); // Find the middle column index
// Find the row with the maximum value in the middle column
let max_row = 0;
for (let i = 0; i < numRows; ++i) {
if (mat[i][mid_col] > mat[max_row][mid_col]) {
max_row = i;
}
}
// Check if the left neighbor is greater, if it exists
let left_is_bigger = mid_col - 1 >= low && mat[max_row][mid_col] < mat[max_row][mid_col - 1];
// Check if the right neighbor is greater, if it exists
let right_is_bigger = mid_col + 1 <= high && mat[max_row][mid_col] < mat[max_row][mid_col + 1];
// If the maximum value is greater than both neighbors, return it as the peak
if (!left_is_bigger && !right_is_bigger) {
return [max_row, mid_col];
}
// If the left neighbor is greater, search in the left half
else if (left_is_bigger) {
high = mid_col - 1;
}
// If the right neighbor is greater, search in the right half
else {
low = mid_col + 1;
}
}
// If no peak is found, return [-1, -1]
return [-1, -1];
};Complexity Analysis of Peak Element II Solution
Time Complexity: O(n log(m))
Initialization:
- Determining the number of rows (m) and columns (n) is O(1).
Main Loop:
- The main loop runs while low <= high. There are total m columns and in each iteration search space is halved meaning.
m → m/2 → m/4 → m/8 → ... → 1 - This means the time complexity of the loop is O(log m)
Calculate Middle Column:
- Calculating the middle column index is O(1).
Find Maximum in Middle Column:
- Finding the maximum element in the middle column requires traversing all rows, which takes O(n).
Check Neighbors and Decision Making:
- Checking the neighbors of the maximum element and making a decision is O(1).
Total Complexity:
- The main loop runs O(log m) times, and in each iteration, finding the maximum in the middle column takes O(m). Therefore, the total complexity is O(n log(m)).
Space Complexity: O(1)
Auxiliary Space Complexity:
It refers to the space complexity caused by the extra data structures we use to solve the problem.
- Initialization:
- Determining the number of rows m and columns n uses a constant amount of space, i.e., O(1).
- Main Loop Variables:
- Variables such as low, high, mid_col, max_row, and the boolean flags for neighbor checks all use O(1) space.
- Finding the Maximum in Column:
- The loop to find the maximum value in the middle column uses a loop variable that consumes O(1) space.
Thus, the auxiliary space complexity is O(1).
Total Space Complexity:
The total space complexity includes the space required by the input matrix and the auxiliary space.
- Since the matrix itself occupies O(n×m)space and the auxiliary space is O(1), the total space complexity is: O(n×m) + O(1) = O(n×m)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array num, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
You are given a 0-indexed array mountain. Your task is to find all the peaks in the mountain array.
Return an array that consists of indices of peaks in the given array in any order.
Notes:
- A peak is defined as an element that is strictly greater than its neighboring elements.
- The first and last elements of the array are not a peak.