Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Find A Peak Element

Moderate

0/80

Contributed by

59 upvotes

Problem statement

You are given a 0-indexed 2-D grid ‘g’ of size ‘n’ X ‘m’, where each cell contains a positive integer, and adjacent cells are distinct.

You need to find the location of a peak element in it. If there are multiple answers, find any of them.

A peak element is a cell with a value strictly greater than all its adjacent cells.

Assume the grid to be surrounded by a perimeter of ‘-1s’.

You must write an algorithm that works in O(n * log(m)) or O(m * log(n)) complexity.

Note:

In the output, you will see '0' or '1', where '0' means your answer is wrong, and '1' means your answer is correct.

Example:

Input: 'n' = 2, 'm' = 2
'g' = [[8, 6], [10, 1]]

Output: 1

Sample Explanation: Only one peak element is present at [1, 0].

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains two integers, ‘n’ and ‘m’, representing the size of grid ‘g’.   
Next ‘n’ lines contain ‘m’ integers, the elements of the current row.

Output Format:

Return an array with 2 elements [x,y], the location of the peak element (in 0-based indexing). ‘1’ will be printed for the correct answer, and ‘0’ for the incorrect answer.

Sample Input 1:

2 2
8 6
10 1

Sample Output 1:

Explanation of sample output 1:

For g = [[8,6],[10,1]],
Answer = [1,0].
There is only one peak element that is present at [1,0].

Sample Input 2:

Sample Output 2:

Explanation of sample output 2:

For g = [[1, 2, 3], [4, 5, 6], [7, 8, 9]],
Answer = [2,2].
There is only one peak element that is present at [2,2].

Constraints:

1 <= n, m <= 500    
1 <= g[i][j] <= 10^9    
Adjacent cells are distinct.
Time Limit: 1 sec

Hint 1

Hint 2

Which element will always be a peak element?

Approaches (2)

Approach 1

Approach 2

Finding Maximum Element

Approach:

The element with the maximum value in the whole grid will always be a peak element. Thus we can perform a linear search on the whole grid and find the location of the maximum element.

Algorithm:

Initialise ‘indx’ = 0, ‘indy’ = ‘0’
for ‘i’ from 0 to N-1:
- for ‘j’ from ‘0’ to ‘M-1’
  - if ( g[indx][indy] < g[i][j])
    - indx = i
    - indy = j
return {indx,indy}

Time Complexity

O(n*m), where 'n' and ‘m’ are the number of rows and columns in 'g'.

We are iterating through all the elements of ‘g’ once.

Therefore, the total time complexity is O(n*m).

Space Complexity

O(1)

We are not utilising any extra space.

Thus, the total space complexity is O(1).

(100% EXP penalty)

Find A Peak Element

Niraj Jayesh Mandaliya

Interview problems

Find A peak element in 2D Matrix || O(n * log(M)) || Binary Search || java

public static int maxOfColumn(int [][]MATRIX, int n, int m, int mid){

int max = 0;

int index = 0;

for(int i=0; i<=n-1; i++){

if(MATRIX[i][mid] > max) {

max = MATRIX[i][mid];

index = i;

}

return index;

}

public static int[] findPeakGrid(int [][]MATRIX){

int n = MATRIX.length;

int m = MATRIX[0].length;

int low = 0;

int high = m-1;

while(low <= high){

int mid = (low+high)/2;

int row = maxOfColumn(MATRIX, n, m, mid);

int left = mid - 1 >= 0 ? MATRIX[row][mid-1] : -1;

int right = mid + 1 < m ? MATRIX[row][mid+1] : -1;

if(left < MATRIX[row][mid] && right < MATRIX[row][mid]){

return new int[]{row, mid};

}

else if(left > MATRIX[row][mid]){

high = mid - 1;

}

else {

low = mid + 1;

}

return new int[]{-1,-1};

}

14 views

0 replies

0 upvotes

Janvi Patidar

Interview problems

JAVA SOLUTION USING BINARY SEARCH (OPTIMAL SOLUTION)

public class Solution {

public static int findMaxelement(int[][]mat , int n , int m , int col){

int maxValue=-1;

int index=-1;

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

if(mat[i][col]>maxValue){

maxValue=mat[i][col];

index=i;

}

return index;

}

public static int[] findPeakGrid(int [][]G){

// Write your code here.

int n=G.length;

int m=G[0].length;

int low=0 , high=m-1;

while(low<=high){

int mid=(low+high)/2;

int rowMax=findMaxelement(G, n, m, mid);

int left=0<=mid-1?G[rowMax][mid-1]:-1;

int right=mid+1<m?G[rowMax][mid+1]:-1;

if(G[rowMax][mid]>left && G[rowMax][mid]>right){

return new int[] {rowMax , mid};

}

else if(G[rowMax][mid]<left) high=mid-1;

else low=mid+1;

}

return new int[]{-1 , -1};

}

56 views

0 replies

0 upvotes

Anup Kumar

Interview problems

Code

int findmax(vector<vector<int>> &g, int n, int m, int col)

{

int maxElement = -1;

int idx = -1;

for (int i = 0; i < n; i++)

{

if (g[i][col] > maxElement)

{

maxElement = g[i][col];

idx = i;

}

return idx;

}

vector<int> findPeakGrid(vector<vector<int>> &g)

{

int row = g.size();

int col = g[0].size();

int low = 0, high = col - 1;

while (low <= high)

{

int mid = (low + high) / 2;

int maxRow = findmax(g, row, col, mid);

int left = mid - 1 >= 0 ? g[maxRow][mid - 1] : -1;

int right = mid + 1 < col ? g[maxRow][mid + 1] : -1;

if (g[maxRow][mid] > right && g[maxRow][mid] > left)

{

return {maxRow, mid};

}

else if (g[maxRow][mid] < left)

{

high = mid - 1;

}

else

{

low = mid + 1;

}

return {-1, -1};

}

77 views

0 replies

0 upvotes

Rahul

Interview problems

Find A Peak Element

def findPeakGrid(g: [[int]]) -> [int]:


    def find_peak_in_column(mid_col):
        max_val = -1
        max_row = -1
        for i in range(len(g)):
            if g[i][mid_col] > max_val:
                max_val = g[i][mid_col]
                max_row = i
        return max_row


    def is_peak(row, col):
        current_val = g[row][col]
        top_val = g[row - 1][col] if row - 1 >= 0 else -1
        bottom_val = g[row + 1][col] if row + 1 < len(g) else -1
        left_val = g[row][col - 1] if col - 1 >= 0 else -1
        right_val = g[row][col + 1] if col + 1 < len(g[0]) else -1


        return current_val > top_val and current_val > bottom_val and current_val > left_val and current_val > right_val


    def binary_search_peak(start, end, find_peak_fn):
        while start < end:
            mid = start + (end - start) // 2
            max_row = find_peak_fn(mid)
            if is_peak(max_row, mid):
                return [max_row, mid]
            elif g[max_row][mid + 1] > g[max_row][mid]:
                start = mid + 1
            else:
                end = mid
        max_row = find_peak_fn(start)
        return [max_row, start]


    n = len(g)
    m = len(g[0])


    # Binary search on columns
    peak_candidate = binary_search_peak(0, m - 1, find_peak_in_column)
    
    return peak_candidate

python

31 views

0 replies

0 upvotes

Rohan Sunwar

Interview problems

c++ beats 99%

#include<bits/stdc++.h>

int findmax(vector<vector<int>> &g, int n, int m, int col)

{

int maxEl = -1;

int index = -1;

for (int i = 0; i < n; i++)

{

if (g[i][col] > maxEl)

{

maxEl = g[i][col];

index = i;

}

return index;

}

vector<int> findPeakGrid(vector<vector<int>> &g)

{

int n = g.size();

int m = g[0].size();

int low = 0, high = m - 1;

while (low <= high)

{

int mid = (low + high) / 2;

int maxRow = findmax(g, n, m, mid);

int left = mid - 1 >= 0 ? g[maxRow][mid - 1] : -1;

int right = mid + 1 < m ? g[maxRow][mid + 1] : -1;

if (g[maxRow][mid] > right && g[maxRow][mid] > left)

{

return {maxRow, mid};

}

else if (g[maxRow][mid] < left)

{

high = mid - 1;

}

else

{

low = mid + 1;

}

return {-1, -1};

}

318 views

0 replies

0 upvotes

Ajay Harishchandra Beldar

Interview problems

now this is some valid solution to all type of matrix

int find_max(vector<vector<int>> &g,int col,int row)

{

int index=-1;

int maxi=-1;

for(int i=0;i<row;i++)

{

if(g[i][col]>maxi)

{

maxi=g[i][col];

index=i;

}

return index;

}

vector<int> findPeakGrid(vector<vector<int>> &g){

// Write your code here.

int n=g.size();

int m=g[0].size();

int low=0;

int high=m-1;

while(low<=high)

{

int mid=low+(high-low)/2;

int maxi_index=find_max(g,mid,n);

int left=-1;

if(mid-1>=0)

{

left=g[maxi_index][mid-1];

}

int right=-1;

if(mid+1<m)

{

right=g[maxi_index][mid+1];

}

if(g[maxi_index][mid] > left && g[maxi_index][mid] > right)

{

return {maxi_index,mid};

}

else if(g[maxi_index][mid] < left)

{

high=mid-1;

}

else

{

low=mid+1;

}

return {-1,-1};

}

110 views

0 replies

0 upvotes

Ajay Harishchandra Beldar

Interview problems

given problem not constructed well || all test cases matrix rows are just sorted in ascending or descending order all answers are from first colum or last column

vector<int> findPeakGrid(vector<vector<int>> &g){

// Write your code here.

int n = g.size();

int m = g[0].size();

int ans1 = -1 , ans2 = -1;

int max = g[0][0];

for(int i=0; i<n; i++)

{

if(g[i][m-1]>=max)

{

max=g[i][m-1];

ans1=i;

ans2=m-1;

}

else if(g[i][0]>=max)

{

max=g[i][0];

ans1=i;

ans2=0;

}

return {ans1, ans2};

}

52 views

0 replies

0 upvotes

Komal Rauniyar

Interview problems

Python solution

def findmaxelement(g,mid,n):

maxel=-9999

index=-1

for i in range(n):

if g[i][mid]>maxel:

maxel=g[i][mid]

index=i

return index

def findPeakGrid(g: [[int]]) -> [int]:

# Write your code here.

n=len(g)

m=len(g[0])

low=0

high=m-1

res=[-1,-1]

while(low<=high):

mid=(low+high)//2

row=findmaxelement(g,mid,n)

left=g[row][mid-1] if mid-1>=0 else -1

right=g[row][mid+1] if mid+1<m else -1

if (g[row][mid]>left and g[row][mid]>right):

res[0]=row

res[1]=mid

return res

elif (g[row][mid]<left):

high=mid-1

else:

low=mid+1

return res

45 views

0 replies

0 upvotes

Linesh Mishra

Interview problems

Find A Peak Element

Python solution

def findPeakGrid(g: [[int]]) -> [int]:

# Write your code here.

n = len(g)

m = len(g[0])

ans1, ans2 = -1, -1

max_val = g[0][0]

for i in range(n):

low, high = 0, m - 1

while low <= high:

mid = (low + high) // 2

if g[i][mid] >= max_val:

max_val = g[i][mid]

ans1, ans2 = i, mid

low = mid + 1

else:

high = mid - 1

return [ans1, ans2]

pass

68 views

0 replies

1 upvote

Ishika Aggarwal

Interview problems

EASY JAVA SOLUTION

public class Solution {

public static int findMaxIndex(int [][]mat, int n, int m, int col){

int maxValue=-1;

int index=-1;

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

if(mat[i][col]>maxValue){

maxValue=mat[i][col];

index=i;

}

return index;

}

public static int[] findPeakGrid(int [][]G){

// Write your code here.

int n=G.length;

int m=G[0].length;

int low=0;

int high=m-1;

while(low<=high){

int mid=(low+high)/2;

int maxRowIndex = findMaxIndex(G,n,m,mid);

int left= 0<=mid-1 ? G[maxRowIndex][mid-1] : -1;

int right= mid+1<m ? G[maxRowIndex][mid+1] : -1;

if(G[maxRowIndex][mid]>left && G[maxRowIndex][mid]>right){

return new int[] {maxRowIndex,mid};

}

else if(G[maxRowIndex][mid] < left) high=mid-1;

else low=mid+1;

}

return new int[] {-1,-1};

}

201 views

0 replies

0 upvotes

Console