LeetCode 1901 - Find a Peak Element II

The problem requires finding a peak element in a 2D matrix. A peak element is defined as an element that is strictly greater than its adjacent neighbors to the top, bottom, left, and right.

leetcodemediumarraybinary-searchmatrix

LeetCode Problem 1901

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Matrix

Solution

Problem Understanding

The problem requires finding a peak element in a 2D matrix. A peak element is defined as an element that is strictly greater than its adjacent neighbors to the top, bottom, left, and right. The matrix is guaranteed to have no two adjacent elements equal, which simplifies comparisons. The input is a 2D list mat of size m x n with values between 1 and 10^5. The matrix is conceptually surrounded by a perimeter of -1, ensuring boundary elements can still be peaks without extra checks.

The expected output is the coordinates [i, j] of any peak element. The problem requires an algorithm with O(m log n) or O(n log m) time complexity, which rules out a brute-force scan of all elements (O(m*n)), especially since m and n can be as large as 500.

Important edge cases include matrices that are a single row or a single column, matrices with peaks on the boundaries, and matrices with multiple possible peaks.

Approaches

The brute-force approach would iterate over every element in the matrix and check if it is larger than its four neighbors. This guarantees a correct solution but requires O(m*n) time, which is too slow for the problem constraints.

The optimal approach leverages a binary search strategy along either rows or columns. The key observation is that if you find the global maximum in the middle column and it is not a peak, then a peak must exist in the half of the matrix that contains a neighbor larger than this maximum. This allows us to reduce the search space by half each iteration, achieving O(m log n) or O(n log m) time depending on whether we search by columns or rows. For consistency, we will describe the column-based binary search.

Approach Time Complexity Space Complexity Notes
Brute Force O(m*n) O(1) Check all elements for peak property
Optimal O(m*log n) O(1) Binary search over columns, check row maximum per column

Algorithm Walkthrough

  1. Initialize two pointers left = 0 and right = n-1 representing the column boundaries.
  2. While left <= right, calculate the middle column mid = (left + right) // 2.
  3. Find the row index of the maximum element in column mid. This element is a candidate for a peak.
  4. Compare this maximum element with its immediate left and right neighbors (if they exist).

a. If the element is larger than both neighbors, it is a peak. Return [row_index, mid].

b. If the left neighbor is larger, move the search to the left half right = mid - 1.

c. If the right neighbor is larger, move the search to the right half left = mid + 1. 5. Repeat steps 2-4 until a peak is found. Binary search ensures the loop converges.

Why it works: Each iteration either finds a peak or moves to a half that contains a neighbor larger than the candidate. Since the matrix is bounded and no two adjacent cells are equal, this guarantees that the search will always lead to a peak.

Python Solution

from typing import List

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        left, right = 0, n - 1

        while left <= right:
            mid = (left + right) // 2
            # Find the row with the maximum element in the middle column
            max_row = max(range(m), key=lambda r: mat[r][mid])
            # Check neighbors
            left_val = mat[max_row][mid - 1] if mid - 1 >= 0 else -1
            right_val = mat[max_row][mid + 1] if mid + 1 < n else -1
            if mat[max_row][mid] > left_val and mat[max_row][mid] > right_val:
                return [max_row, mid]
            elif left_val > mat[max_row][mid]:
                right = mid - 1
            else:
                left = mid + 1

The Python code uses binary search over columns. The max() function with a key lambda identifies the row with the column maximum. Neighbor comparisons determine whether the candidate is a peak or if the search should continue left or right. This ensures O(m*log n) time complexity.

Go Solution

func findPeakGrid(mat [][]int) []int {
    m, n := len(mat), len(mat[0])
    left, right := 0, n - 1

    for left <= right {
        mid := (left + right) / 2
        maxRow := 0
        for i := 1; i < m; i++ {
            if mat[i][mid] > mat[maxRow][mid] {
                maxRow = i
            }
        }
        leftVal, rightVal := -1, -1
        if mid-1 >= 0 {
            leftVal = mat[maxRow][mid-1]
        }
        if mid+1 < n {
            rightVal = mat[maxRow][mid+1]
        }
        if mat[maxRow][mid] > leftVal && mat[maxRow][mid] > rightVal {
            return []int{maxRow, mid}
        } else if leftVal > mat[maxRow][mid] {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return nil
}

The Go implementation mirrors Python but handles array indexing explicitly. We predefine leftVal and rightVal as -1 for out-of-bound columns. Integer division ensures correct mid calculation.

Worked Examples

Example 1: mat = [[1,4],[3,2]]

Step 1: left=0, right=1, mid=0. Column 0 maximum is 3 at row 1. Compare neighbors: left=-1, right=2. Since 3 > -1 but 3 > 2 is false, move right left=1.

Step 2: mid=1. Column 1 maximum is 4 at row 0. Neighbors: left=1, right=-1. 4 > 1 and 4 > -1, so [0,1] is returned.

Example 2: mat = [[10,20,15],[21,30,14],[7,16,32]]

Step 1: left=0, right=2, mid=1. Column 1 maximum is 30 at row 1. Neighbors: left=21, right=14. 30 > 21 and 30 > 14, so [1,1] is returned immediately.

Complexity Analysis

Measure Complexity Explanation
Time O(m*log n) Each iteration finds the max in a column (O(m)) and reduces search space by half over columns (O(log n))
Space O(1) Only constant variables are used

The dominant operation is scanning a column for its maximum; since binary search halves the columns each step, the overall time is O(m log n).

Test Cases

# Provided examples
assert Solution().findPeakGrid([[1,4],[3,2]]) in [[0,1],[1,0]]  # multiple valid peaks
assert Solution().findPeakGrid([[10,20,15],[21,30,14],[7,16,32]]) in [[1,1],[2,2]]  # multiple valid peaks

# Edge cases
assert Solution().findPeakGrid([[1]]) == [0,0]  # single element
assert Solution().findPeakGrid([[1,2,3]]) == [0,2]  # single row
assert Solution().findPeakGrid([[1],[2],[3]]) == [2,0]  # single column

# Larger test case
mat = [[i+j for j in range(5)] for i in range(5)]
assert Solution().findPeakGrid(mat) in [[4,4]]  # peak at bottom-right
Test Why
[[1,4],[3,2]] Multiple peaks, validates algorithm finds any
[[10,20,15],[21,30,14],[7,16,32]] Multiple peaks in larger matrix
[[1]] Single element, simplest edge case
[[1,2,3]] Single row, tests column max logic
[[1],[2],[3]] Single column, tests row scanning

Edge Cases

Single element matrix: The matrix [[1]] has only one element, which is trivially a peak. The algorithm correctly identifies this because the neighbor checks default to -1 for out-of-bounds indices.

Single row or column: A single row or column may have the peak at the boundaries. The binary search handles this because it checks left and right neighbors for columns and treats missing neighbors as -1.

Multiple possible peaks: The matrix may have more than one peak. The algorithm guarantees finding any peak, not necessarily the first. This is consistent with problem requirements and ensures correctness even when multiple valid answers exist.