Two-dimensional Peak finding problem

Algorithmic thinking, Algorithms, Programming

Before reading this, I would recommend reading the previous post on the one-dimensional version of the Peak finding problem.

Definition

A peak in a 2D array (or matrix) is an element that is greater than or equal to all of its adjacent elements.

Brute-force approach

The brute-force approach is simple: compare each element with its adjacent elements until a peak is found.

Worst-case time complexity: Θ(m*n)

First attempt

For a 2D array arr[] with n rows and m columns, we can use a variation of the 1D peak finding algorithm to find the 2D peak:

• Pick the middle column j = m/2.
• Find a 1D-peak at arr[i, j]
• Use arr[i, j] as a start point on row i to find 1D peak on row i.

However, you’ll see that this doesn’t work very well and it will lead to a wrong peak value.

Eg:
14, 6, 12
15, 9, 11
16, 4, 18

We end up with 15, which is not a 2D peak.

Second attempt

We can fix this quite easily by fixing our second step:

• Pick the middle column j = m/2
• Find global maximum on column j at arr[i, j]
• Compare (i, j − 1), (i, j), (i, j + 1)
• Pick the left column if (i, j − 1) > (i,j)
• Pick the right column if (i, j + 1) > (i,j)
• arr[i,j] is a 2D-peak if neither condition holds (trivial)
• Solve the new problem with half the number of columns until there is a single column is left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from typing import List

"""
Best-case: Θ(1)
Worst-case: T(n) = T(n/2) + Θ(n) = Θ(n * lg n)
Average-case: Θ(n * lg n)
"""

def find_2d_peak(arr: List[float], start: int, end: int) -> Tuple[int, int]:
    def global_max(arr: List[float], column: int) -> int:
        m: int = 0
        for row in range(1, len(arr)):
            if arr[row][column] > arr[m][column]:
                m = row
        return m

    if start == end:
        return (global_max(arr, start), start)

    mid: int = (start + end) // 2
    col_max: int = global_max(arr, mid)

    if arr[col_max][mid + 1] >= arr[col_max][mid]:
        return find_2d_peak(arr, mid + 1, end)
    elif arr[col_max][mid - 1] >= arr[col_max][mid]:
        return find_2d_peak(arr, start, mid - 1)
    else:
        return (col_max, mid)

Summary

This is the end of the Peak finding problem. I am currently nearing the end of my website’s development. The process has been a slow but rewarding one, and I look forward to releasing the website and getting feedback from y’all!