Find Peak Element

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

Use two pointers, low initialized to 0 and high initialized to m - 1, to define the search range across columns.
Execute a loop where low is less than or equal to high and compute mid as (low + high) / 2 to determine the middle column.
Utilize maxElement() function to find the row index where the middle column(mid) has the maximum element and let's call it 'row'.
If element at cell(row,mid) is greater than both neighbors, return {row, mid} as the peak element coordinates.
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.
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):

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.
Iterate through each row of the 2D array, find the maximum element in the column 'col' of matrix and return its index.

#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;
}
import java.util.*;

class Solution {
    
    /* Helper function to find the index of the row
    with the maximum element in a given column*/
    public int maxElement(int[][] arr, int col) {
        int n = arr.length;
        int max = Integer.MIN_VALUE;
        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) {
                max = arr[i][col];
                index = i;
            }
        }
        //Return the index
        return index; 
    }
    
    /* Function to find a peak element in 
    the 2D matrix using binary search */
    public int[] findPeakGrid(int[][] arr) {
        int n = arr.length;   
        int m = arr[0].length; 
        
        /* 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] : Integer.MIN_VALUE;
            int right = mid + 1 < m ? arr[row][mid + 1] : Integer.MIN_VALUE;
            
            /* Check if the middle element 
            is greater than its neighbors */
            if (arr[row][mid] > left && arr[row][mid] > right) {
                return new int[]{row,mid};  
            } 
            else if (left > arr[row][mid]) {
                high = mid - 1;  
            } 
            else {
                low = mid + 1;
            }
        }
        
        // Return -1 if no peak element is found
        return new int[]{-1,-1};  
    }

    public static void main(String[] args) {
        // Example usage
        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 = new Solution();
        
        // Call findPeakGridfunction and print the result
        System.out.println("The row of peak element is "+sol.findPeakGrid(mat)[0]+" and column of the peak element is "+sol.findPeakGrid(mat)[1]);
    }
}
class Solution:
    """Helper function to find the index of the row
    with the maximum element in a given column"""
    def maxElement(self, arr, col):
        n = len(arr)
        max_val = float('-inf')
        index = -1
        
        """Iterate through each row to find the
        maximum element in the specified column"""
        for i in range(n):
            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 """
    def findPeakGrid(self, arr):
        n = len(arr)    
        m = len(arr[0])  
        
        """Initialize the lower bound for 
        and upper bound for binary search"""
        low = 0           
        high = m - 1      
        
        # Perform binary search on columns
        while low <= high:
            mid = (low + high) // 2 
            
            """Find the index of the row with the 
            maximum element in the middle column"""
            row = self.maxElement(arr, mid)
            
            """ Determine the elements to left and 
            right of middle element in the found row """
            left = arr[row][mid - 1] if mid - 1 >= 0 else float('-inf')
            right = arr[row][mid + 1] if mid + 1 < m else float('-inf')
            
            """ Check if the middle element 
            is greater than its neighbors """
            if arr[row][mid] > left and arr[row][mid] > right:
                return [row, mid]  
            elif left > arr[row][mid]:
                high = mid - 1  
            else:
                low = mid + 1  
        
        # Return [-1, -1] if no peak element is found
        return [-1, -1]

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
sol = Solution()

# Call findPeakGrid function and print the result
peak = sol.findPeakGrid(mat)
print(f"The row of peak element is {peak[0]} and column of the peak element is {peak[1]}")
class Solution {
    /*Helper function to find the index of the row
    with the maximum element in a given column*/
    maxElement(arr, col) {
        let n = arr.length;
        let max_val = Number.MIN_SAFE_INTEGER;
        let index = -1;
        
        /*Iterate through each row to find the
        maximum element in the specified column*/
        for (let 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 */
    findPeakGrid(arr) {
        let n = arr.length; 
        let m = arr[0].length;  
        
        /*Initialize the lower bound for 
        and upper bound for binary search */
        let low = 0;           
        let high = m - 1;      
        
        // Perform binary search on columns
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);   
            
            /*Find the index of the row with the 
            maximum element in the middle column*/
            let row = this.maxElement(arr, mid);
            
            /*Determine the elements to left and 
            right of middle element in the found row */
            let left = mid - 1 >= 0 ? arr[row][mid - 1] : Number.MIN_SAFE_INTEGER;
            let right = mid + 1 < m ? arr[row][mid + 1] : Number.MIN_SAFE_INTEGER;
            
            /*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];  
    }
}

// Example usage
let 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
let sol = new Solution();

// Call findPeakElement function and print the result
let peak = sol.findPeakGrid(mat);
console.log(`The row of peak element is ${peak[0]} and column of the peak element is ${peak[1]}`);

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).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts