Problem Description

You are given a 2D grid (matrix) where you need to find a peak element. A peak element is defined as an element that is strictly greater than all of its adjacent neighbors (left, right, top, and bottom).

The matrix mat has the following properties:

• It is 0-indexed with dimensions m x n
• No two adjacent cells have equal values (all adjacent elements are different)
• The entire matrix is conceptually surrounded by an outer perimeter with value -1 in each cell

Your task is to find any peak element mat[i][j] and return its position as a length-2 array [i,j].

Time Complexity Requirement: Your algorithm must run in O(m log(n)) or O(n log(m)) time, where m is the number of rows and n is the number of columns.

For example, if an element at position [i,j] has value 10, and its adjacent neighbors have values 5 (left), 7 (right), 3 (top), and 8 (bottom), then this element is a peak because 10 > 5, 10 > 7, 10 > 3, and 10 > 8.

The logarithmic time complexity requirement suggests that a binary search approach should be used rather than checking every element in the matrix.

Intuition

The time complexity requirement of O(m log(n)) or O(n log(m)) immediately suggests we need to use binary search rather than checking all elements. But how can we apply binary search to a 2D grid?

Let's think about what happens when we pick a row and find its maximum element. Suppose we're at row i and the maximum element in this row is at column j. Now we have mat[i][j].

The key insight is to compare mat[i][j] with the element directly below it: mat[i+1][j]. There are two cases:

1. If mat[i][j] > mat[i+1][j]: Since mat[i][j] is already the maximum in its row, it's greater than its left and right neighbors. If it's also greater than the element below, we need to check if it's greater than the element above. If not, then the element above must be even larger. This creates an "upward flow" - we keep moving up to find larger elements. Eventually, we'll reach row 0, where the element has no row above it (conceptually it's bordered by -1), making it a peak. So there must be a peak in rows [0...i].

2. If mat[i][j] < mat[i+1][j]: By similar logic, if the element below is larger, we have a "downward flow". We keep moving down to find larger elements. Eventually, we'll reach the last row where there's no row below (bordered by -1), guaranteeing a peak exists in rows [i+1...m-1].

This observation allows us to eliminate half of the search space with each comparison! We can perform binary search on rows:

• Start with the middle row
• Find the maximum element in that row
• Compare it with the element directly below
• Based on the comparison, we know which half contains a peak
• Continue binary search in that half

The beauty of this approach is that we're guaranteed to find a peak because:

• The matrix is surrounded by -1 values
• No two adjacent cells are equal
• Following the direction of increasing values must eventually lead to a peak (it can't increase forever due to the boundary)

Learn more about Binary Search patterns.

Solution Approach

We implement binary search on the rows of the matrix. Here's the step-by-step approach:

Initialize Binary Search Boundaries:

• Set l = 0 (first row) and r = len(mat) - 1 (last row)
• These represent our search space for rows

Binary Search Process: While l < r:

1. Calculate the middle row: mid = (l + r) >> 1 (using right shift for division by 2)
2. Find the maximum element in row mid and its column index j:
   • j = mat[mid].index(max(mat[mid]))
   • This finds the column position of the maximum value in the current row
3. Compare mat[mid][j] with the element directly below it mat[mid + 1][j]:
   • If mat[mid][j] > mat[mid + 1][j]: The peak must be in rows [0...mid]
     • Update r = mid (search in upper half including current row)
   • Else (mat[mid][j] < mat[mid + 1][j]): The peak must be in rows [mid + 1...m - 1]
     • Update l = mid + 1 (search in lower half excluding current row)

Return the Peak:

• When the loop exits, l == r, meaning we've narrowed down to a single row
• Find the maximum element in this final row: mat[l].index(max(mat[l]))
• Return [l, mat[l].index(max(mat[l]))] as the peak position

Why This Works:

• In each iteration, we eliminate half of the remaining rows
• We're guaranteed to find a peak because:
  • If we move up (when mat[mid][j] > mat[mid + 1][j]), we're moving towards rows where eventually the top boundary (-1) ensures a peak exists
  • If we move down (when mat[mid][j] < mat[mid + 1][j]), we're moving towards rows where eventually the bottom boundary (-1) ensures a peak exists
• The maximum element of the final row l is guaranteed to be a peak because our binary search has ensured it's greater than the element in the adjacent row we came from

Time Complexity: O(m log m + m × n) where finding max in each row takes O(n) and we do this O(log m) times during binary search, plus O(m × n) for the initial max operations. However, if we optimize by caching or using a different approach for finding row maximum, we can achieve O(n log m).

Space Complexity: O(1) as we only use a constant amount of extra space for variables.

Example Walkthrough

Let's walk through finding a peak in this 3×4 matrix:

mat = [[1,  4,  3,  2],
       [9,  5,  6,  7],
       [8, 10, 11, 12]]

Initial Setup:

• l = 0 (first row), r = 2 (last row)
• We need to find a peak element

Iteration 1:

• Calculate middle row: mid = (0 + 2) >> 1 = 1
• Find maximum in row 1: [9, 5, 6, 7]
  • Maximum is 9 at column index 0
  • So we have mat[1][0] = 9
• Compare with element below: mat[1][0] vs mat[2][0]
  • 9 > 8, so the peak must be in rows [0...1]
  • Update r = 1

Iteration 2:

• Now l = 0, r = 1
• Calculate middle row: mid = (0 + 1) >> 1 = 0
• Find maximum in row 0: [1, 4, 3, 2]
  • Maximum is 4 at column index 1
  • So we have mat[0][1] = 4
• Compare with element below: mat[0][1] vs mat[1][1]
  • 4 < 5, so the peak must be in rows [1...1]
  • Update l = 1

Final Step:

• Now l = r = 1, loop exits
• Find maximum in row 1: [9, 5, 6, 7]
  • Maximum is 9 at column index 0
• Return [1, 0]

Verification: Is mat[1][0] = 9 a peak?

• Left neighbor: conceptually -1 (boundary) ✓ 9 > -1
• Right neighbor: mat[1][1] = 5 ✓ 9 > 5
• Top neighbor: mat[0][0] = 1 ✓ 9 > 1
• Bottom neighbor: mat[2][0] = 8 ✓ 9 > 8

Yes! The element 9 at position [1, 0] is indeed a peak.

Note: The algorithm could also find other valid peaks like 12 at [2, 3]. The problem only requires finding any one peak, not all peaks or the global maximum.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log m), where m is the number of rows and n is the number of columns in the matrix. The algorithm uses binary search on the rows, which takes O(log m) iterations. In each iteration, we need to find the maximum element in the current row using max(mat[mid]) and then find its index using mat[mid].index(). Finding the maximum requires traversing all n elements in the row with O(n) time, and finding the index of that maximum requires another O(n) traversal in the worst case. Therefore, each binary search iteration has O(n) complexity, resulting in a total time complexity of O(n × log m).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables l, r, mid, and j, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Maximum Element Finding

The current implementation calls max(mat[mid_row]) and then mat[mid_row].index(max(mat[mid_row])), which scans the row twice - once to find the maximum value and once to find its index. This is inefficient and doubles the work.

Solution:

# Instead of:
max_col_index = mat[mid_row].index(max(mat[mid_row]))

# Use:
max_col_index = 0
for j in range(1, len(mat[mid_row])):
    if mat[mid_row][j] > mat[mid_row][max_col_index]:
        max_col_index = j

2. Incorrect Time Complexity Analysis

The stated time complexity in the explanation is misleading. The actual complexity is O(m × n + log(m) × n) which simplifies to O(m × n) due to the initial scanning, not the desired O(n log m).

Solution: Remove any unnecessary full matrix scans and ensure you're only examining O(log m) rows, each taking O(n) time to process.

3. Boundary Check Assumption

The code assumes mid_row + 1 always exists when comparing, but doesn't explicitly handle the case when mid_row might be the last row during iteration.

Solution:

# Add explicit boundary checking:
if mid_row + 1 < len(mat):
    if mat[mid_row][max_col_index] > mat[mid_row + 1][max_col_index]:
        right = mid_row
    else:
        left = mid_row + 1
else:
    # mid_row is the last row, so it could contain the peak
    right = mid_row

4. Not Verifying the Peak Property

The algorithm assumes the final element found is a peak without verifying all four neighbors. While mathematically correct due to the binary search logic, this can lead to confusion during debugging or when requirements change.

Solution: Add a verification step (especially useful during development/debugging):

def is_peak(mat, i, j):
    m, n = len(mat), len(mat[0])
    val = mat[i][j]
    # Check all four neighbors (with boundary handling)
    if i > 0 and mat[i-1][j] >= val: return False
    if i < m-1 and mat[i+1][j] >= val: return False
    if j > 0 and mat[i][j-1] >= val: return False
    if j < n-1 and mat[i][j+1] >= val: return False
    return True

5. Column-wise vs Row-wise Binary Search Choice

The solution arbitrarily chooses to binary search on rows. If n << m (many more rows than columns), it would be more efficient to binary search on columns instead.

Solution: Choose the dimension to binary search based on matrix shape:

def findPeakGrid(self, mat):
    m, n = len(mat), len(mat[0])
  
    # Choose more efficient approach based on dimensions
    if m >= n:
        # Binary search on rows (current approach)
        return self.binarySearchRows(mat)
    else:
        # Binary search on columns (transposed logic)
        return self.binarySearchColumns(mat)