Problem Statement

Given a 0-indexedn x m matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the array [i, j]. A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom.

Assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell.

Examples

Example 1:

Input: mat = [
              [10, 20, 15],
              [21, 30, 14],
              [7, 16, 32]
             ]
Output: [1, 1]

Explanation: The value at index [1, 1] is 30, which is a peak element because all its neighbours are smaller or equal to it. Similarly, {2, 2} can also be picked as a peak.

Example 2:

Input: mat = [
              [10, 7],
              [11, 17]
             ]
Output: [1, 1]

Explanation: The element at index (1, 1) is the peak element.

Example 3:

Input: mat = [
              [1, 2, 3],
              [4, 5, 6],
              [7, 8, 9]
             ]
Output: [2, 2]

Explanation: The element at index (2, 2) is the peak element.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

It is simple just traverse the entire matrix. For every element check if it is greater than its neighbors i.e., top element, bottom element, right element, left element.

Edges Cases:

• At row 0, top element would be -1.
• At row n-1, bottom element would be -1.
• At col 0, left element would be -1.
• At col m-1, right element would be -1.

Code:

class Solution {
public:
    // Function to find a peak element in the 2D matrix
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int n = mat.size();    // Number of rows
        int m = mat[0].size(); // Number of columns

        // Iterate through every element of the matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Get the values of the neighboring cells
                int top = (i == 0) ? -1 : mat[i - 1][j];         // Top neighbor
                int bottom = (i == n - 1) ? -1 : mat[i + 1][j];  // Bottom neighbor
                int left = (j == 0) ? -1 : mat[i][j - 1];        // Left neighbor
                int right = (j == m - 1) ? -1 : mat[i][j + 1];   // Right neighbor

                int current = mat[i][j]; // Current element

                // Check if the current element is greater than all its neighbors
                if (current > top && current > bottom && current > left && current > right) {
                    return {i, j}; // Return the position of the peak
                }
            }
        }

        // Return {-1, -1} if no peak is found (this should never happen in a valid input)
        return {-1, -1};
    }
};

Complexity Analysis:

• Time Complexity: O(N*M)
  • Outer loop runs for N times (rows).
  • Inner loops runs for M times (columns).
• Space Complexity: O(1)

2️⃣ Binary Search

Intuition:

• The brute-force solution to this problem involves searching for the largest element in the matrix by iterating through all cells. Since the question suggests that no two adjacent elements are equal, the largest element will be the peak element. However, this approach has a time complexity of O(N*M), where N is the number of rows and M is the number of columns.
• To optimize the previous solution, binary search can be employed. The intuition behind the peak element in 1-D array can be used here. For each element (mid), we check if it is greater than its previous and next elements. If so, mid is identified as a peak element. Alternatively, if mid is smaller than its previous element, a peak must exist on the left side, so the right half is eliminated. Similarly, if mid is less than the next element, a peak must exist on the right side, so the left half is eliminated. This approach trims down the search space in each iteration, thereby enhancing the time complexity.
• Here, for a 2-D array, the search will start from range [0, col-1], where col is the total number of columns in each row. First, find the 'mid' and find out the largest element in column 'mid' and apply the same approach as a 1-D array. That is, if the element at mid is a peak, return it. Otherwise, if the left element is greater, eliminate the right half; otherwise, eliminate the left half.

Approach:

Working of findPeakElement(matrix):

1. Use two pointers, low initialized to 0 and high initialized to m - 1, to define the search range across columns.
2. Execute a loop where low is less than or equal to high and compute mid as (low + high) / 2 to determine the middle column.
3. Utilize maxElement() function to find the row index where the middle column(mid) has the maximum element and let's call it 'row'.
4. If element at cell(row,mid) is greater than both neighbors, return {row, mid} as the peak element coordinates.
5. If the left neighbor is greater than the element at cell(row,mid), adjust high to mid - 1 to search in the left half. Otherwise, adjust low to mid + 1 to search in the right half.
6. If the loop exits without finding a peak (i.e., low > high), return {-1, -1} to indicate no peak element exists in the matrix.

Working of maxElement(matrix,col):

1. Start by initializing n to arr.length, which gives the number of rows in the 2D array arr. Initialize max to Integer.MIN_VALUE to store the maximum value found in the specified column col and also initialize index to -1, which will store the index of the row containing the maximum element in the specified column.
2. Iterate through each row of the 2D array, find the maximum element in the column 'col' of matrix and return its index.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Helper function to find the index of the row
    with the maximum element in a given column*/
    int maxElement(vector<vector<int>>& arr, int col) {
        int n = arr.size();
        int max_val = INT_MIN;
        int index = -1;
        
        /* Iterate through each row to find the
        maximum element in the specified column*/
        for (int i = 0; i < n; i++) {
            if (arr[i][col] > max_val) {
                max_val = arr[i][col];
                index = i;
            }
        }
        // Return the index
        return index;
    }
    
    /* Function to find a peak element in 
     the 2D matrix using binary search */
    vector<int> findPeakGrid(vector<vector<int>>& arr) {
        int n = arr.size();     
        int m = arr[0].size();  
        
        /* Initialize the lower bound for 
        and upper bound for binary search */
        int low = 0;           
        int high = m - 1;      
        
        // Perform binary search on columns
        while (low <= high) {
            int mid = (low + high) / 2;  
            
            /* Find the index of the row with the 
            maximum element in the middle column*/
            int row = maxElement(arr, mid);
            
            /* Determine the elements to left and 
            right of middle element in the found row */
            int left = mid - 1 >= 0 ? arr[row][mid - 1] : INT_MIN;
            int right = mid + 1 < m ? arr[row][mid + 1] : INT_MIN;
            
            /* Check if the middle element 
             is greater than its neighbors */
            if (arr[row][mid] > left && arr[row][mid] > right) {
                return {row, mid};  
            } 
            else if (left > arr[row][mid]) {
                high = mid - 1;  
            } 
            else {
                low = mid + 1;
            }
        }
        
        // Return {-1, -1} if no peak element is found
        return {-1, -1};  
    }
};

int main() {
    // Example usage
    vector<vector<int>> mat = {
        {4, 2, 5, 1, 4, 5},
        {2, 9, 3, 2, 3, 2},
        {1, 7, 6, 0, 1, 3},
        {3, 6, 2, 3, 7, 2}
    };
    
    // Create an instance of Solution class
    Solution sol;
    
    // Call findPeakGridfunction and print the result
    vector<int> peak = sol.findPeakGrid(mat);
    cout << "The row of peak element is " << peak[0] << " and column of the peak element is " << peak[1] << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N * logM), where N is the number of rows in the matrix, M is the number of columns in each row. The complexity arises because binary search is performed on the columns, and for each mid column, a linear search through the rows is executed to find the maximum element.
• Space Complexity: As no additional space is used, so the Space Complexity is O(1).