Find Peak Element-II | Binary Search (BS-26)

1. Problem Statement & Context

Building upon the 1D peak element problem (BS-16), this chapter extends the search for a peak element into a 2D Matrix.

• The Core Definition: In a 2D matrix where no two adjacent cells share the same value, an element is classified as a Peak Element if and only if it is strictly greater than all four of its immediate directional counterparts (Top, Bottom, Left, and Right).
• Boundary Condition: Any out-of-bounds neighbor (such as an element on the outer edge lacking a top or left neighbor) is treated as having a value of -1.
• Multiple Peaks: A matrix may contain multiple valid peak elements. The objective is to return the row and column indices of any one valid peak.

Real-Life Analogy: Navigating a Mountain Range (Topography)

Imagine flying over a vast, rugged mountain range represented by a 2D grid of elevations. Instead of blindly walking up and down every single hill on the map, you drop onto a specific cross-section (column), locate the highest peak along that ridge, and check if neighboring ridges are higher or lower. If a neighboring ridge is higher, you drop your search space and shift entirely toward that higher range, drastically cutting down your exploration time.

2. Naive Approach & Its Limitations

The Brute-Force Scan

The most intuitive approach is to iterate through every single element in the $N \times M$ 2D matrix. For every cell encountered, inspect its four directional neighbors (Top, Bottom, Left, Right).

• Worst-Case Time Complexity: $\mathcal{O}(N \times M \times 4)$, which simplifies to $\mathcal{O}(N \times M)$ because every element is visited and checked across four directions.
• The Largest Element Shortcut: Some might argue: "Why not just find the absolute largest element in the entire 2D matrix and return that?" While the absolute maximum in a matrix is guaranteed to be a peak (since it's larger than all neighbors, including out-of-bound -1 edges), scanning for it still requires traversing all $N \times M$ cells.
• Interview Verdict: This fails to impress an interviewer because it fails to optimize for speed when $N$ and $M$ grow large. We need an approach that avoids visiting every element.

3. Core Mental Model: Bridging 1D Binary Search to 2D

To optimize beyond $\mathcal{O}(N \times M)$, we must discard portions of the search space without visiting them. Since we are dealing with a grid, can we apply binary search?

Yes! Instead of performing binary search on all individual cells, we perform Binary Search on the Columns of the 2D matrix.

The Search Elimination Intuition

1. Pick a mid-column: mid = (low + high) / 2.
2. Find the row index of the maximum element within that specific mid column.
3. Check the left and right horizontal neighbors of this maximum element:
   • If the element is greater than both its left and right horizontal neighbors, we have found our Peak Element.
   • If the left neighbor is larger, a peak is guaranteed to exist somewhere in the left half of the columns. We eliminate the right half (high = mid - 1).
   • If the right neighbor is larger, a peak is guaranteed to exist somewhere in the right half of the columns. We eliminate the left half (low = mid + 1).

4. Step-by-Step Flow Walkthrough

Let's trace an execution walkthrough on a sample 2D matrix:

Row 0: [ 10,  20,  15 ]
Row 1: [ 21,  30,  14 ]
Row 2: [ 7,   16,  32 ]

• Step 1: Initialize search space across columns.
  • low = 0 (Column 0)
  • high = 2 (Column 2)
• Step 2: Calculate mid column:
  • mid = (0 + 2) / 2 = 1 (Column 1: [20, 30, 16])
• Step 3: Find the maximum element in Column 1 (mid = 1):
  • Max element is 30, located at row = 1.
• Step 4: Check horizontal neighbors of 30 (at row 1, col 1):
  • Left neighbor: matrix[1][0] = 21
  • Right neighbor: matrix[1][2] = 14
  • Is 30 > 21 and 30 > 14? Yes!
• Step 5: Return indices [1, 1] as our peak element.

5. Pseudocode Implementation

The following pseudocode implements the optimal column-based binary search:

def findPeakGrid(matrix):
    n = len(matrix)
    m = len(matrix[0])
    
    low = 0
    high = m - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        # Step 1: Find the row index with the maximum element in the 'mid' column
        max_row_index = findMaxRow(matrix, n, mid)
        
        # Step 2: Get left and right values with boundary safety checks (-1 for out-of-bounds)
        left_val = matrix[max_row_index][mid - 1] if mid - 1 >= 0 else -1
        right_val = matrix[max_row_index][mid + 1] if mid + 1 < m else -1
        current_val = matrix[max_row_index][mid]
        
        # Step 3: Check if current element is a peak
        if current_val > left_val and current_val > right_val:
            return [max_row_index, mid]
        elif current_val < left_val:
            # Eliminate right half
            high = mid - 1
        else:
            # Eliminate left half
            low = mid + 1
            
    return [-1, -1] # Dummy return for safety

def findMaxRow(matrix, n, col):
    max_val = -1
    max_index = -1
    for i in range(n):
        if matrix[i][col] > max_val:
            max_val = matrix[i][col]
            max_index = i
    return max_index

Note: The helper function findMaxRow scans down the specific mid column of length $N$, which takes $\mathcal{O}(N)$ time per binary search iteration.

6. Complexity Analysis

Summary and Key Takeaways

• Problem Extension: Finding a peak in 2D requires an element to be greater than four neighbors (Top, Bottom, Left, Right) instead of two.
• Flaw of Brute Force: Scanning every cell takes $\mathcal{O}(N \times M)$ time, which fails to exploit sorted or searchable patterns in interview settings.
• The Binary Search Shift: Instead of searching every cell, perform binary search across the columns while scanning rows to locate local maximums.
• Why Max Element?: Choosing the maximum element in the examined column guarantees vertical superiority (top and bottom), reducing the 2D problem into a 1D-like horizontal decision between left and right halves.
• Boundary Handling: Out-of-bounds indices are treated as -1, ensuring edge cases are safely evaluated without throwing index errors.
• Optimal Efficiency: The combined approach runs in $\mathcal{O}(N \log M)$ time and $\mathcal{O}(1)$ auxiliary space, representing the optimal solution for this problem.