<p>A <strong>peak</strong> element in a 2D grid is an element that is <strong>strictly greater</strong> than all of its <strong>adjacent </strong>neighbors to the left, right, top, and bottom.</p>

<p>Given a <strong>0-indexed</strong> <code>m x n</code> matrix <code>mat</code> where <strong>no two adjacent cells are equal</strong>, find <strong>any</strong> peak element <code>mat[i][j]</code> and return <em>the length 2 array </em><code>[i,j]</code>.</p>

<p>You may assume that the entire matrix is surrounded by an <strong>outer perimeter</strong> with the value <code>-1</code> in each cell.</p>

<p>You must write an algorithm that runs in <code>O(m log(n))</code> or <code>O(n log(m))</code> time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/1.png" style="width: 206px; height: 209px;" /></p>

<pre>
<strong>Input:</strong> mat = [[1,4],[3,2]]
<strong>Output:</strong> [0,1]
<strong>Explanation:</strong>&nbsp;Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/07/3.png" style="width: 254px; height: 257px;" /></strong></p>

<pre>
<strong>Input:</strong> mat = [[10,20,15],[21,30,14],[7,16,32]]
<strong>Output:</strong> [1,1]
<strong>Explanation:</strong>&nbsp;Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 500</code></li>
	<li><code>1 &lt;= mat[i][j] &lt;= 10<sup>5</sup></code></li>
	<li>No two adjacent cells are equal.</li>
</ul>

from typing import List
class Solution:
    def find_peak_in_column(self,matrix, col):
        # Find the maximum element in the given column
        max_row = 0
        for i in range(len(matrix)):
            if matrix[i][col] > matrix[max_row][col]:
                max_row = i
        return max_row
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        n = len(mat)  # Number of rows
        m = len(mat[0])  # Number of columns

        left = 0
        right = m-1
        while left<=right:
            mid = (left+right)//2
            # row = self.find_peak_in_column(mat,mid)
            row = self.find_peak_in_column(mat, mid)

            if (mid == 0 or mat[row][mid] >= mat[row][mid-1]) and\
                (mid == m-1 or mat[row][mid] >= mat[row][mid+1]):
                return [row,mid]
            elif mid > 0 and mat[row][mid-1] > mat[row][mid]:
                right = mid-1
            else:
                left = mid+1
        
        return []
        # # Traverse the entire matrix
        # for i in range(n):
        #     for j in range(m):
        #         # Compare with neighbors (taking care of boundary conditions)
        #         if (i == 0 or mat[i][j] > mat[i-1][j]) and \
        #            (i == n-1 or mat[i][j] > mat[i+1][j]) and \
        #            (j == 0 or mat[i][j] > mat[i][j-1]) and \
        #            (j == m-1 or mat[i][j] > mat[i][j+1]):
        #             return [i, j]  # Return the first peak found

        # return []  # If no peak is found (which shouldn't happen according to the problem)
 # Return an empty list if no peak is found

        # n = len(mat)
        # m = len(mat[0])

        # for i in range(1,n-1):
        #     for j in range(1,m-1):
        #         if mat[i][j] > mat[i][j+1] and mat[i][j] > mat[i+1][j] and mat[i][j] > mat[i][j-1] and mat[i][j] > mat[i-1][j]:
        #             return [i,j]

        # return []
47600