<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>

class Solution:
    def getColMax_idx(self, mat, col):
        index = -1
        maximum = -inf
        for row in range(len(mat)):
            if mat[row][col] > maximum:
                index = row
                maximum = mat[row][col]
        return index
    
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        num_rows = len(mat)
        num_cols = len(mat[0])
        
        left, right = 0, num_cols-1
        
        #check middle column:
        while left <= right:
            mid = (left + right) // 2
            #find the max entry of the col
            colmax_idx = self.getColMax_idx(mat, mid)
            
            
            #find the left and right neighbors of this max column entry
            
            neighbor_left = mat[colmax_idx][mid - 1] if mid != 0 else -1
            neighbor_right = mat[colmax_idx][mid+1] if mid != num_cols-1 else -1
            pot_peak = mat[colmax_idx][mid] 
            
            if pot_peak > neighbor_left and pot_peak > neighbor_right:
                return [colmax_idx, mid]
            elif pot_peak <= neighbor_right:
                left = mid+1
            else:
                right = mid
           

            
            
                
                
            
        
        
        
    '''
    mat = [[1,4], [3*,2]]
    
    left, right = 0, 1
    #begin while loop
    
    mid = 0
    colmax_idx = 1 
    mat[mid][colmax_idx] = mat[0][1] = 3
    
    left = -1
    right = mat[1][1] = 2 
    
    Here it returns [0,1]
    ------------------------
    mat = [[3,4], [1,2]]
    
    left, right = 0, 1
    mid = 0
    colmax_idx = 0
    mat[mid][colmax_idx] = mat[0][0] = 3
    
    neighbor_left = -1
    neighbor_right = mat[mid][colmax] = mat[0][1] = 4
    
    left, right = 1,1
    mid = 1
    colmax_idx = 0 
    
    neighbor
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    mat = [[A11, ..., A1n], ..., [Am1, ..., Amn]]
    
    Considering first row: [A11, ..., A1n]
                -1
     A1(mid-1)-A1mid-A1(mid+1)
                 |
               A2mid
               
                -1
               1-1--1
                 |
                 2
               
    O(mlog(n))  
    Let f(mat, start, end) be a function that finds peak of mat 
        1) Pick middle column find max O(m) element peak_cand
            if start = end, return peak_cand location
        2) If peak_cand is peak then return peak_cand_location
        3) If peak_cand <= right_neighbor then call f(mat, right_col, end)
        4) If peak_cand <= left_neighor then call f(mat, start, mid_col)
        
        
        if colmax_idx == 0:
                left_neighbor = -1
                right_neighbor = mat[mid][colmax_idx+1]
            elif mid == num_cols-1:
                left_neighbor = mat[mid-1][colmax_idx]
                right_neighbor = -1
            else:
                left_neighbor = mat[mid-1][colmax_idx]
                right_neighbor = mat[mid+1][colmax_idx]
            #check if this is a peak:
            if mat[mid][colmax_idx] > left_neighbor and mat[mid][colmax_idx] > right_neighbor:
                return [mid, colmax_idx]
            elif mat[mid][colmax_idx] <= right_neighbor:
                #then the right side of the matrix has a peak
                left = mid + 1
            else:
                right = mid
        
    '''
        
903