# Two Dimensional Peak Finding

# 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:

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

This reduces the search space in one dimension.

## Algorithm

```id="peak2d-1"
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

```id="py-peak2d"
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
```

```id="go-peak2d"
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
}
```