Leetcode 1901: Find a Peak Element II
In a given 2D grid, a peak element is an element that is greater than all of its adjacent elements (left, right, top, and bottom). You are given an m x n matrix
mat where no two adjacent elements are equal. Your task is to find and return the coordinates of any peak element. The grid is surrounded by a perimeter filled with -1.Problem
Approach
Steps
Complexity
Input: A matrix of integers, mat, representing the grid.
Example: mat = [[10, 20, 15], [21, 30, 14], [7, 16, 32]]
Constraints:
• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 10^5
• No two adjacent cells are equal.
Output: Return the coordinates of any peak element in the grid.
Example: [1, 1]
Constraints:
• Coordinates of any peak element in the grid.
Goal: Find the coordinates of any peak element.
Steps:
• Perform binary search on columns.
• For each column, find the row with the largest element.
• Check if the element is greater than its left and right neighbors.
• Adjust the search space based on comparisons with neighbors.
Goal: The matrix is bounded by -1 and contains no two adjacent equal elements.
Steps:
• 1 <= m, n <= 500
• No two adjacent elements in the matrix are equal.
Assumptions:
• The matrix is non-empty and valid.
• There will always be at least one peak element.
• Input: Input: mat = [[10, 20, 15], [21, 30, 14], [7, 16, 32]]
• Explanation: The element at [1, 1] (30) is a peak because it is greater than its neighbors (20, 15, 21, 14).
Approach: We can use binary search to find a peak element in O(m log(n)) or O(n log(m)) time.
Observations:
• The problem can be approached using a divide-and-conquer technique, such as binary search.
• By reducing the search space at each step, we can efficiently find a peak element.
Steps:
• Perform binary search on columns.
• For each mid column, identify the row with the largest value.
• Compare with adjacent cells to determine if the element is a peak.
• Adjust the search space accordingly.
Empty Inputs:
• An empty matrix is not allowed based on constraints.
Large Inputs:
• Handle matrices with dimensions close to 500 x 500.
Special Values:
• Ensure proper handling when elements are at the edges of the matrix.
Constraints:
• The matrix is guaranteed to have no two adjacent equal cells.
vector<int> findPeakGrid(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
int l = 0, r = n - 1;
while(l <= r) {
int mid = l + (r - l + 1) / 2;
int row = 0;
for(int i = 0; i < m; i++)
row = mat[i][mid] >= mat[row][mid]? i: row;
int isRightLarger = mid + 1 <= r ? mat[row][mid + 1] > mat[row][mid]: false;
int isLeftLarger = mid - 1 >= l ? mat[row][mid - 1] > mat[row][mid]: false;
if(!isRightLarger && !isLeftLarger)
return vector<int>{row, mid};
if(isRightLarger) l = mid + 1;
else r = mid - 1;
}
return vector<int>{-1, -1};
}
1 : Function Definition
vector<int> findPeakGrid(vector<vector<int>>& mat) {
The function 'findPeakGrid' is defined to take a 2D matrix as input and return a vector of integers representing the peak's coordinates.
2 : Variable Initialization
int m = mat.size(), n = mat[0].size();
Here, we initialize 'm' to the number of rows and 'n' to the number of columns in the matrix.
3 : Binary Search Setup
int l = 0, r = n - 1;
We initialize two variables 'l' and 'r' to represent the left and right boundaries for the binary search on columns.
4 : While Loop
while(l <= r) {
This while loop will continue to iterate as long as there is a valid range between 'l' and 'r'.
5 : Mid Calculation
int mid = l + (r - l + 1) / 2;
Here, we calculate the middle column index 'mid' to split the matrix and search for the peak.
6 : Row Search
int row = 0;
We initialize a variable 'row' to track the row that contains the maximum value at the current 'mid' column.
7 : Iterating Rows
for(int i = 0; i < m; i++)
This for loop iterates over each row of the matrix to find the row where the element in the 'mid' column is the largest.
8 : Row Selection
row = mat[i][mid] >= mat[row][mid]? i: row;
If the current element in the 'mid' column is greater than the previous maximum, update the 'row' variable.
9 : Right Comparison
int isRightLarger = mid + 1 <= r ? mat[row][mid + 1] > mat[row][mid]: false;
We check if the element to the right of 'mid' in the same row is larger. If it is, we will move the binary search range to the right.
10 : Left Comparison
int isLeftLarger = mid - 1 >= l ? mat[row][mid - 1] > mat[row][mid]: false;
We check if the element to the left of 'mid' in the same row is larger. If it is, we will move the binary search range to the left.
11 : Peak Check
if(!isRightLarger && !isLeftLarger)
If neither the left nor the right elements are larger, we have found the peak element, so we return the coordinates.
12 : Returning Peak
return vector<int>{row, mid};
Return the coordinates of the peak element as a vector.
13 : Adjusting Search Range
if(isRightLarger) l = mid + 1;
If the right neighbor is larger, update the left boundary 'l' to search the right half of the matrix.
14 : Adjusting Search Range
else r = mid - 1;
If the left neighbor is larger, update the right boundary 'r' to search the left half of the matrix.
15 : Return Invalid Result
return vector<int>{-1, -1};
If no peak is found, return an invalid result indicating failure to find a peak.
Best Case: O(m log(n))
Average Case: O(m log(n))
Worst Case: O(m log(n))
Description: Binary search is applied on columns, ensuring logarithmic time complexity in one dimension.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant since we do not use any additional space for storing intermediate results.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus