Greedy Ascent Algorithm - Finding Peak in 2D Array

Formal Problem Statement - Find a peak in a 2D array, where a is a 2D-peak iff a ≥ b, a ≥ d, a ≥ c, a ≥ e. If there are more than one peaks, just return one of them.

Greedy Ascent Algorithm works on the principle, that it selects a particular element to start with. Then it begins traversing across the array, by selecting the neighbour with higher value. If there is no neighbour with a higher value than the current element, it just returns the current element.

Logically, this algorithm is correct, as it returns the element - which has none of it's neighbours greater than the current element.

After a bit of thought, we can come to the conclusion that, in a worst case, the whole array will be transversed. Hence, its time complexity is Θ(mn).

Finally, the code using recursion would be,

#include <iostream>
using namespace std;

int a[100][100], n, m;

int recur(int i, int j) {
    if (i > 0 && a[i - 1][j] > a[i][j]) return recur(i - 1, j);
    else if (i < n - 1 && a[i + 1][j] > a[i][j]) return recur(i + 1, j);
    else if (j > 0 && a[i][j - 1] > a[i][j]) return recur(i, j - 1);
    else if (j < n - 1 && a[i][j + 1] > a[i][j]) return recur(i, j + 1);
    else return a[i][j];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    cout << recur(0, 0);
    return 0;
}

Sources: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf