Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
Problem:
https://www.geeksforgeeks.org/problems/find-the-peak-element-in-a-2d-matrix/1
Find the Peak Element in a 2D Matrix
Difficulty: Medium Accuracy: 28.51%
Given a 2D matrix mat[][], identify any peak element within the matrix.
An element is considered a peak if it is greater than or equal to its four immediate neighbors: top, bottom, left, and right. For corner and edge elements, any missing neighbors are treated as having a value of negative infinity.
Note: A peak element is not necessarily the global maximum, it only needs to satisfy the condition relative to its adjacent elements. Multiple peak elements may exist, return any one of them.
Note that the driver code will print true if you return the correct position of peak element, else it will print false.
Examples:
Input: mat[][] = [[10, 20, 15],
[21, 30, 14],
[7, 16, 32]]
Output: true
Explanation: One of the peak element is 30 at index (1, 1), which is greater than or equal to all its valid neighbors: Left = 21, Right = 14, Top = 20, Bottom = 16. So, it satisfies the peak condition. Alternatively, (2, 2) with value 32 also qualifies as a peak.
Input: mat[][] = [[17, 7],
[11, 10]]
Output: true
Explanation: 17 is the only peak element at index (0, 0). Its neighbors are: Right= 7, Bottom = 11. Since 17 is greater than or equal to both (and top/left are out of bounds), it qualifies as a peak element.
Constraint:
1 ≤ n × m ≤ 106
-106 ≤ mat[i][j] ≤ 106
Solution:
class Solution:
def findPeakGrid(self, mat):
n = len(mat)
m = len(mat[0])
l, r = 0, m - 1
while l <= r:
mid = (l + r) // 2
max_row = 0
for i in range(0, n):
if mat[i][mid] > mat[max_row][mid]:
max_row = i
left = mat[max_row][mid-1] if mid-1 >= 0 else float('-inf')
right = mat[max_row][mid+1] if mid+1 < m else float('-inf')
if mat[max_row][mid] >= left and mat[max_row][mid] >= right:
return [max_row, mid]
elif left > mat[max_row][mid]:
r = mid - 1
else:
l = mid + 1
return [-1, -1]
Top comments (0)