#1901

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find a Peak Element II

Locate any peak in a 2D matrix using binary search across rows or columns for efficient discovery and verification.

Problem Statement

Given a 0-indexed m x n matrix mat where no two adjacent cells have equal values, identify any peak element mat[i][j]. A peak is strictly greater than its left, right, top, and bottom neighbors, assuming a surrounding border of -1.

Return the coordinates of a peak as a length 2 array [i,j]. The matrix can be large, so brute-force checking all elements is inefficient; the solution should exploit binary search over the valid answer space to quickly locate a peak.

Examples

Example 1

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

Output: [0,1]

Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.

Example 2

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

Output: [1,1]

Both 30 and 32 are peak elements so [1,1] and [2,2] are both acceptable answers.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 500
1 <= mat[i][j] <= 105
No two adjacent cells are equal.

Solution Approach

Binary Search on Columns

Pick the middle column, find the maximum element in that column, and compare it with its neighbors to decide which half of the matrix to continue searching. Repeat until a peak is found.

Binary Search on Rows

If the number of columns is less than rows, perform the binary search on the middle row instead, selecting the row maximum and comparing with vertical neighbors, then reduce the search space accordingly.

Termination and Peak Validation

When the chosen element is greater than all four adjacent neighbors, return its coordinates. This ensures correctness while reducing time complexity compared to a full traversal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on whether binary search is done on rows or columns: O(m log n) if searching columns or O(n log m) if searching rows. Space complexity is O(1) as no extra structures are needed beyond indices.

What Interviewers Usually Probe

Expect discussion of why binary search is valid over the matrix instead of brute-force scanning.
Watch for whether candidates correctly identify the maximum in the middle row or column each iteration.
Check if they handle edge cases with single-row, single-column, or boundary elements efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to compare the middle element with all four neighbors, missing a valid peak.
Incorrectly handling equal values or assuming adjacent cells can be equal, which violates constraints.
Not adjusting search direction properly when the peak is not in the current maximum column or row.

Follow-up variants

Find all peak elements instead of returning any single peak.
Solve on a toroidal grid where the edges wrap around instead of using a border of -1.
Adapt the approach for 3D matrices using similar binary search on slices.

FAQ

What defines a peak element in Find a Peak Element II?

A peak element is one that is strictly greater than its four immediate neighbors: left, right, top, and bottom, assuming a surrounding -1 border.

Can multiple peaks exist in the matrix?

Yes, the matrix may contain several peaks; returning any one peak is acceptable for this problem.

Why is binary search valid in this 2D matrix?

Binary search works because by selecting a middle row or column and comparing its maximum with neighbors, we can systematically eliminate half the search space each step.

What is the time complexity using binary search?

Searching columns gives O(m log n) and searching rows gives O(n log m), which is much faster than O(m*n) brute-force traversal.

How do I handle edge elements in the matrix?

Treat the outer perimeter as -1 so comparisons at edges remain valid without extra conditional checks.

terminal

Solution

Solution 1: Binary Search

Let $m$ and $n$ be the number of rows and columns of the matrix, respectively.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        l, r = 0, len(mat) - 1
        while l < r:
            mid = (l + r) >> 1
            j = mat[mid].index(max(mat[mid]))
            if mat[mid][j] > mat[mid + 1][j]:
                r = mid
            else:
                l = mid + 1
        return [l, mat[l].index(max(mat[l]))]

Continue Practicing

#1970 last day where you can still cross #1631 path with minimum effort #2258 escape the spreading fire