Matrix: Given a 2D matrix, find the peak element.

Problem Statement:

You are given a 2D matrix of size n * m, you need to find the peak element.

An element is a peak element if it is greater than or equal to its 4 neighbors i.e left, right, top and bottom.

If more than one peak element, return any one of them.

There will be atleast one peak element in the array

For the corner elements, for missing neighbor considered of -ve inf value.

You need to print the index of the element

Example:

Input:

1 2 3
2 9 4
5 6 2

Output:

1, 1

The value at 1,1  is "9", that is the peak element

Solution :

Solution is a brute force approach.

For each element check if the element is greater than to all of its neighbors.

Time Complexity: O(rows * columns))
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;


vector<int> solution(vector<vector<int>>& mat) {

    int n = mat.size();
    int m = mat[0].size();

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {

        	//assume current element as peak element
            int curr = mat[i][j];
            bool isPeak = true;

            if (i > 0 && mat[i - 1][j] > curr)
                isPeak = false;

            if (i + 1 < n && mat[i + 1][j] > curr)
                isPeak = false;

            if (j > 0 && mat[i][j - 1] > curr)
                isPeak = false;

            if (j + 1 < m  && mat[i][j + 1] > curr)
                isPeak = false;

            if (isPeak)
                return {i, j};
        }
    }

    return {-1, -1};
}


int main() {
    vector<vector<int>> mat = {
        {1, 2, 3},
        {2, 9, 4},
        {5, 6, 2}
    };

    vector<int> peak = solution(mat);
    cout << peak[0] << " " << peak[1] << endl;
    return 0;
}

Output

1 1