Two Dimensional Peak Finding

Two dimensional peak finding finds a position in a matrix whose value is at least as large as its neighbors in four directions.

Given a matrix $A$ of size $n \times m$, a position $(i, j)$ is a peak if:

$A[i][j] \ge A[i-1][j]$
$A[i][j] \ge A[i+1][j]$
$A[i][j] \ge A[i][j-1]$
$A[i][j] \ge A[i][j+1]$

Out of bounds neighbors are treated as $-\infty$.

Problem

Given a matrix $A$, find a peak position $(i, j)$.

Key Idea

Use divide and conquer on columns:

Pick the middle column
Find the maximum element in that column
Compare it with its left and right neighbors
Move to the half that contains a larger neighbor

This reduces the search space in one dimension.

Algorithm

peak_finding_2d(A):
    n = number of rows
    m = number of columns

    l = 0
    r = m - 1

    while l <= r:
        mid = (l + r) // 2

        # find row index of maximum element in column mid
        max_row = 0
        for i from 1 to n - 1:
            if A[i][mid] > A[max_row][mid]:
                max_row = i

        left = A[max_row][mid - 1] if mid > 0 else -inf
        right = A[max_row][mid + 1] if mid < m - 1 else -inf

        if A[max_row][mid] >= left and A[max_row][mid] >= right:
            return (max_row, mid)
        elif left > A[max_row][mid]:
            r = mid - 1
        else:
            l = mid + 1

    return (-1, -1)

Example

Let

$$ A = \begin{bmatrix} 10 & 8 & 10 & 10
14 & 13 & 12 & 11
15 & 9 & 11 & 21
16 & 17 & 19 & 20 \end{bmatrix} $$

One possible peak is:

$$ (2, 0) \text{ with value } 15 $$

Another is:

$$ (3, 2) \text{ with value } 19 $$

The algorithm may return any valid peak.

Correctness

At each step, the algorithm considers the maximum element in the middle column.

If this element is greater than or equal to its horizontal neighbors, it is a peak because it is also the largest in its column.

If a neighbor on one side is larger, then there must be a peak in that direction. This follows from the same reasoning as in one dimensional peak finding: moving toward a larger neighbor eventually leads to a peak.

The algorithm discards half of the columns each iteration while maintaining that a peak exists in the remaining region.

Complexity

Let $n$ be rows and $m$ be columns.

operation	cost
find column max	$O(n)$
iterations	$O(\log m)$
total	$O(n \log m)$

Space:

$$ O(1) $$

Variants

variant	idea
row-based	divide by rows instead of columns
recursive	explicit divide and conquer recursion
full 2D binary	more complex but not necessary

Comparison

dimension	method	time
1D	peak finding	$O(\log n)$
2D	column divide	$O(n \log m)$

When to Use

Finding local maxima in grids
Image processing
Terrain analysis
Optimization on discrete surfaces

Notes

The returned peak is not necessarily global maximum
Works for any rectangular matrix
Can be extended to higher dimensions

Implementation

def peak_finding_2d(a):
    if not a or not a[0]:
        return -1, -1

    n, m = len(a), len(a[0])
    l, r = 0, m - 1

    while l <= r:
        mid = (l + r) // 2

        max_row = 0
        for i in range(n):
            if a[i][mid] > a[max_row][mid]:
                max_row = i

        left = a[max_row][mid - 1] if mid > 0 else float('-inf')
        right = a[max_row][mid + 1] if mid < m - 1 else float('-inf')

        if a[max_row][mid] >= left and a[max_row][mid] >= right:
            return max_row, mid
        elif left > a[max_row][mid]:
            r = mid - 1
        else:
            l = mid + 1

    return -1, -1

import "math"

func PeakFinding2D(a [][]int) (int, int) {
    if len(a) == 0 || len(a[0]) == 0 {
        return -1, -1
    }

    n, m := len(a), len(a[0])
    l, r := 0, m-1

    for l <= r {
        mid := (l + r) / 2

        maxRow := 0
        for i := 0; i < n; i++ {
            if a[i][mid] > a[maxRow][mid] {
                maxRow = i
            }
        }

        left := math.MinInt
        if mid > 0 {
            left = a[maxRow][mid-1]
        }

        right := math.MinInt
        if mid < m-1 {
            right = a[maxRow][mid+1]
        }

        if a[maxRow][mid] >= left && a[maxRow][mid] >= right {
            return maxRow, mid
        } else if left > a[maxRow][mid] {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }

    return -1, -1
}