# Find a peak element in matrix

The problem is to find a peak element in a given matrix. A peak element is an element that is not smaller than its neighbors. In a 2D matrix, an element is a peak if it is greater than or equal to its adjacent elements in all four directions (top, bottom, left, and right).

## Example

Consider the following 4x4 matrix:

``````10  15  11  20
13  16  27  25
11  29  28  15
21  13  15  14``````

In this matrix, the number 29 is a peak element since it is greater than its adjacent elements (27, 28, 21, and 15).

## Idea to Solve the Problem

To find a peak element in the given matrix, we can follow these steps:

1. Define a function `isSafe` to check if a given element is a peak by comparing it with its adjacent elements.
2. Define a function `peakPoint` to find a peak element in the matrix: a. Iterate through each element in the matrix. b. For each element, check if it is a peak using the `isSafe` function. c. If a peak element is found, print it.
3. In the `main` function, create a matrix and call the `peakPoint` function to find and print the peak element.

## Pseudocode

``````isSafe(matrix, i, j):
if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j]:
return false
if i + 1 < N and matrix[i + 1][j] > matrix[i][j]:
return false
if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j]:
return false
if j + 1 < N and matrix[i][j + 1] > matrix[i][j]:
return false
return true

peakPoint(matrix):
a = -1
b = -1
for i from 0 to N:
for j from 0 to N:
if isSafe(matrix, i, j):
a = i
b = j
if a != -1 and b != -1:
print "Result:", matrix[a][b]

main:
matrix = {
{10, 15, 11, 20},
{13, 16, 27, 25},
{11, 29, 28, 15},
{21, 13, 15, 14}
}
peakPoint(matrix)``````

## Program

``````//  C program for
//  Find a peak element in matrix
#include <stdio.h>

#define N 4
int isSafe(int matrix[N][N], int i, int j)
{
// 4 neighbors
// top bottom left and right,
if (i - 1 >= 0)
{
// Top element
if (matrix[i - 1][j] > matrix[i][j])
{
return 0;
}
}
if (i + 1 < N)
{
// Bottom element
if (matrix[i + 1][j] > matrix[i][j])
{
return 0;
}
}
if (j - 1 >= 0)
{
// Left element
if (matrix[i][j - 1] > matrix[i][j])
{
return 0;
}
}
if (j + 1 < N)
{
// Right element
if (matrix[i][j + 1] > matrix[i][j])
{
return 0;
}
}
return 1;
}
void peakPoint(int matrix[N][N])
{
int a = -1;
int b = -1;

// Row
for (int i = 0; i < N &&
a == -1 && b == -1; ++i)
{
// Col
for (int j = 0; j < N &&
a == -1 && b == -1;
++j)
{
if (isSafe(matrix, i, j))
{
a = i;
b = j;
// break
}
}
}
if (a != -1 && b != -1)
{
printf("\n Result : %d", matrix[a][b]);
}
}
int main(int argc, char const *argv[])
{
int matrix[N][N] = {
{
10 , 15 , 11 , 20
},
{
13 , 16 , 27 , 25
},
{
11 , 29 , 28 , 15
},
{
21 , 13 , 15 , 14
}
};
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
peakPoint(matrix);
return 0;
}

``````

#### Output

`` Result : 29``
``````/*
Java Program for
Find a peak element in matrix
*/
class PeakPoint
{
public boolean isSafe(int[][] matrix,
int i, int j, int row, int col)
{
// 4 neighbors
// top bottom left and right,
if (i - 1 >= 0)
{
// Top element
if (matrix[i - 1][j] > matrix[i][j])
{
return false;
}
}
if (i + 1 < row)
{
// Bottom element
if (matrix[i + 1][j] > matrix[i][j])
{
return false;
}
}
if (j - 1 >= 0)
{
// Left element
if (matrix[i][j - 1] > matrix[i][j])
{
return false;
}
}
if (j + 1 < col)
{
// Right element
if (matrix[i][j + 1] > matrix[i][j])
{
return false;
}
}
return true;
}
public void findPeakPoint(int[][] matrix)
{
int a = -1;
int b = -1;
int row = matrix.length;
int col = matrix[0].length;
// Row
for (int i = 0; i < row && a == -1 && b == -1; ++i)
{
// Col
for (int j = 0; j < col && a == -1 && b == -1; ++j)
{
if (isSafe(matrix, i, j, row, col))
{
a = i;
b = j;
}
}
}
if (a != -1 && b != -1)
{
System.out.print("\n Result : " + matrix[a][b]);
}
}
public static void main(String[] args)
{
int[][] matrix = {
{
10 , 15 , 11 , 20
},
{
13 , 16 , 27 , 25
},
{
11 , 29 , 28 , 15
},
{
21 , 13 , 15 , 14
}
};
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}
}``````

#### Output

`` Result : 29``
``````// Include header file
#include <iostream>
#define N 4
using namespace std;
/*
C++ Program for
Find a peak element in matrix
*/
class PeakPoint
{
public:
bool isSafe(int matrix[N][N],
int i, int j)
{
// 4 neighbors
// top bottom left and right,
if (i - 1 >= 0)
{
// Top element
if (matrix[i - 1][j] > matrix[i][j])
{
return false;
}
}
if (i + 1 < N)
{
// Bottom element
if (matrix[i + 1][j] > matrix[i][j])
{
return false;
}
}
if (j - 1 >= 0)
{
// Left element
if (matrix[i][j - 1] > matrix[i][j])
{
return false;
}
}
if (j + 1 < N)
{
// Right element
if (matrix[i][j + 1] > matrix[i][j])
{
return false;
}
}
return true;
}
void findPeakPoint(int matrix[N][N])
{
int a = -1;
int b = -1;
// Row
for (int i = 0; i < N && a == -1 && b == -1; ++i)
{
// Col
for (int j = 0; j < N && a == -1 && b == -1; ++j)
{
if (this->isSafe(matrix, i, j))
{
a = i;
b = j;
}
}
}
if (a != -1 && b != -1)
{
cout << "\n Result : " << matrix[a][b];
}
}
};
int main()
{
int matrix[N][N] = {
{
10 , 15 , 11 , 20
} , {
13 , 16 , 27 , 25
} , {
11 , 29 , 28 , 15
} , {
21 , 13 , 15 , 14
}
};
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
return 0;
}``````

#### Output

`` Result : 29``
``````// Include namespace system
using System;
/*
Csharp Program for
Find a peak element in matrix
*/
public class PeakPoint
{
public Boolean isSafe(int[,] matrix,
int i, int j, int row, int col)
{
// 4 neighbors
// top bottom left and right
if (i - 1 >= 0)
{
// Top element
if (matrix[i - 1,j] > matrix[i,j])
{
return false;
}
}
if (i + 1 < row)
{
// Bottom element
if (matrix[i + 1,j] > matrix[i,j])
{
return false;
}
}
if ((j - 1) >= 0)
{
// Left element
if (matrix[i,j - 1] > matrix[i,j])
{
return false;
}
}
if (j + 1 < col)
{
// Right element
if (matrix[i,j + 1] > matrix[i,j])
{
return false;
}
}
return true;
}
public void findPeakPoint(int[,] matrix)
{
int a = -1;
int b = -1;
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);

// Row
for (int i = 0; i < row && a == -1 && b == -1; ++i)
{
// Col
for (int j = 0; j < col && a == -1 && b == -1; ++j)
{
if (this.isSafe(matrix, i, j, row, col))
{
a = i;
b = j;
}
}
}
if (a != -1 && b != -1)
{
Console.Write("\n Result : " + matrix[a,b]);
}
}
public static void Main(String[] args)
{
int[,] matrix = {
{
10 , 15 , 11 , 20
},
{
13 , 16 , 27 , 25
},
{
11 , 29 , 28 , 15
},
{
21 , 13 , 15 , 14
}
};
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}
}``````

#### Output

`` Result : 29``
``````package main
import "fmt"
/*
Go Program for
Find a peak element in matrix
*/
type PeakPoint struct {}
func getPeakPoint() * PeakPoint {
var me *PeakPoint = &PeakPoint {}
return me
}
func(this PeakPoint) isSafe(matrix[][] int,
i int, j int,
row int,
col int) bool {
// 4 neighbors
// top bottom left and right
if i - 1 >= 0 {
// Top element
if matrix[i - 1][j] > matrix[i][j] {
return false
}
}
if i + 1 < row {
// Bottom element
if matrix[i + 1][j] > matrix[i][j] {
return false
}
}
if j - 1 >= 0 {
// Left element
if matrix[i][j - 1] > matrix[i][j] {
return false
}
}
if j + 1 < col {
// Right element
if matrix[i][j + 1] > matrix[i][j] {
return false
}
}
return true
}
func(this PeakPoint) findPeakPoint(matrix[][] int) {
var a int = -1
var b int = -1
var row int = len(matrix)
var col int = len(matrix[0])
// Row
for i := 0 ; i < row && a == -1 && b == -1 ; i++ {
// Col
for j := 0 ; j < col && a == -1 && b == -1 ; j++ {
if this.isSafe(matrix, i, j, row, col) {
a = i
b = j
}
}
}
if a != -1 && b != -1 {
fmt.Print("\n Result : ", matrix[a][b])
}
}
func main() {
var task * PeakPoint = getPeakPoint()
var matrix = [][] int {
{ 10 , 15 , 11 , 20 },
{ 13 , 16 , 27 , 25 },
{ 11 , 29 , 28 , 15 },
{ 21 , 13 , 15 , 14 } }
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}``````

#### Output

`` Result : 29``
``````<?php
/*
Php Program for
Find a peak element in matrix
*/
class PeakPoint
{
public	function isSafe(\$matrix, \$i, \$j, \$row, \$col)
{
// 4 neighbors
// top bottom left and right
if (\$i - 1 >= 0)
{
// Top element
if (\$matrix[\$i - 1][\$j] > \$matrix[\$i][\$j])
{
return false;
}
}
if (\$i + 1 < \$row)
{
// Bottom element
if (\$matrix[\$i + 1][\$j] > \$matrix[\$i][\$j])
{
return false;
}
}
if (\$j - 1 >= 0)
{
// Left element
if (\$matrix[\$i][\$j - 1] > \$matrix[\$i][\$j])
{
return false;
}
}
if (\$j + 1 < \$col)
{
// Right element
if (\$matrix[\$i][\$j + 1] > \$matrix[\$i][\$j])
{
return false;
}
}
return true;
}
public	function findPeakPoint(\$matrix)
{
\$a = -1;
\$b = -1;
\$row = count(\$matrix);
\$col = count(\$matrix[0]);
// Row
for (\$i = 0; \$i < \$row && \$a == -1 && \$b == -1; ++\$i)
{
// Col
for (\$j = 0; \$j < \$col && \$a == -1 && \$b == -1; ++\$j)
{
if (\$this->isSafe(\$matrix, \$i, \$j, \$row, \$col))
{
\$a = \$i;
\$b = \$j;
}
}
}
if (\$a != -1 && \$b != -1)
{
echo("\n Result : ".\$matrix[\$a][\$b]);
}
}
}

function main()
{
\$matrix = array(
array(10, 15, 11, 20),
array(13, 16, 27, 25),
array(11, 29, 28, 15),
array(21, 13, 15, 14)
);
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}
main();``````

#### Output

`` Result : 29``
``````/*
Node JS Program for
Find a peak element in matrix
*/
class PeakPoint
{
isSafe(matrix, i, j, row, col)
{
// 4 neighbors
// top bottom left and right
if (i - 1 >= 0)
{
// Top element
if (matrix[i - 1][j] > matrix[i][j])
{
return false;
}
}
if (i + 1 < row)
{
// Bottom element
if (matrix[i + 1][j] > matrix[i][j])
{
return false;
}
}
if (j - 1 >= 0)
{
// Left element
if (matrix[i][j - 1] > matrix[i][j])
{
return false;
}
}
if (j + 1 < col)
{
// Right element
if (matrix[i][j + 1] > matrix[i][j])
{
return false;
}
}
return true;
}
findPeakPoint(matrix)
{
var a = -1;
var b = -1;
var row = matrix.length;
var col = matrix[0].length;
// Row
for (var i = 0; i < row && a == -1 && b == -1; ++i)
{
// Col
for (var j = 0; j < col && a == -1 && b == -1; ++j)
{
if (this.isSafe(matrix, i, j, row, col))
{
a = i;
b = j;
}
}
}
if (a != -1 && b != -1)
{
process.stdout.write("\n Result : " + matrix[a][b]);
}
}
}

function main()
{
var matrix = [
[10, 15, 11, 20],
[13, 16, 27, 25],
[11, 29, 28, 15],
[21, 13, 15, 14]
];
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}
main();``````

#### Output

`` Result : 29``
``````#    Python 3 Program for
#    Find a peak element in matrix
class PeakPoint :
def isSafe(self, matrix, i, j, row, col) :
#  4 neighbors
#  top bottom left and right
if (i - 1 >= 0) :
#  Top element
if (matrix[i - 1][j] > matrix[i][j]) :
return False

if (i + 1 < row) :
#  Bottom element
if (matrix[i + 1][j] > matrix[i][j]) :
return False

if (j - 1 >= 0) :
#  Left element
if (matrix[i][j - 1] > matrix[i][j]) :
return False

if (j + 1 < col) :
#  Right element
if (matrix[i][j + 1] > matrix[i][j]) :
return False

return True

def findPeakPoint(self, matrix) :
a = -1
b = -1
row = len(matrix)
col = len(matrix[0])
i = 0
#  Row
while (i < row and a == -1 and b == -1) :
j = 0
#  Col
while (j < col and a == -1 and b == -1) :
if (self.isSafe(matrix, i, j, row, col)) :
a = i
b = j

j += 1

i += 1

if (a != -1 and b != -1) :
print("\n Result : ", matrix[a][b], end = "")

def main() :
matrix = [
[10, 15, 11, 20],
[13, 16, 27, 25],
[11, 29, 28, 15],
[21, 13, 15, 14]
]
#    13     27
#      ↖  ↗
#       29
#      ↙  ↘
#    21    15
#    ------------
#    29 is peak

if __name__ == "__main__": main()``````

#### Output

`` Result :  29``
``````#    Ruby Program for
#    Find a peak element in matrix
class PeakPoint
def isSafe(matrix, i, j, row, col)
#  4 neighbors
#  top bottom left and right
if (i - 1 >= 0)
#  Top element
if (matrix[i - 1][j] > matrix[i][j])
return false
end

end

if (i + 1 < row)
#  Bottom element
if (matrix[i + 1][j] > matrix[i][j])
return false
end

end

if (j - 1 >= 0)
#  Left element
if (matrix[i][j - 1] > matrix[i][j])
return false
end

end

if (j + 1 < col)
#  Right element
if (matrix[i][j + 1] > matrix[i][j])
return false
end

end

return true
end

def findPeakPoint(matrix)
a = -1
b = -1
row = matrix.length
col = matrix[0].length
i = 0
#  Row
while (i < row && a == -1 && b == -1)
j = 0
#  Col
while (j < col && a == -1 && b == -1)
if (self.isSafe(matrix, i, j, row, col))
a = i
b = j
end

j += 1
end

i += 1
end

if (a != -1 && b != -1)
print("\n Result : ", matrix[a][b])
end

end

end

def main()
matrix = [
[10, 15, 11, 20],
[13, 16, 27, 25],
[11, 29, 28, 15],
[21, 13, 15, 14]
]
#    13     27
#      ↖  ↗
#       29
#      ↙  ↘
#    21    15
#    ------------
#    29 is peak
end

main()``````

#### Output

`` Result : 29``
``````/*
Scala Program for
Find a peak element in matrix
*/
class PeakPoint()
{
def isSafe(matrix: Array[Array[Int]],
i: Int, j: Int, row: Int, col: Int): Boolean = {
// 4 neighbors
// top bottom left and right
if (i - 1 >= 0)
{
// Top element
if (matrix(i - 1)(j) > matrix(i)(j))
{
return false;
}
}
if (i + 1 < row)
{
// Bottom element
if (matrix(i + 1)(j) > matrix(i)(j))
{
return false;
}
}
if (j - 1 >= 0)
{
// Left element
if (matrix(i)(j - 1) > matrix(i)(j))
{
return false;
}
}
if (j + 1 < col)
{
// Right element
if (matrix(i)(j + 1) > matrix(i)(j))
{
return false;
}
}
return true;
}
def findPeakPoint(matrix: Array[Array[Int]]): Unit = {
var a: Int = -1;
var b: Int = -1;
var row: Int = matrix.length;
var col: Int = matrix(0).length;
var i: Int = 0;
// Row
while (i < row && a == -1 && b == -1)
{
var j: Int = 0;
// Col
while (j < col && a == -1 && b == -1)
{
if (isSafe(matrix, i, j, row, col))
{
a = i;
b = j;
}
j += 1;
}
i += 1;
}
if (a != -1 && b != -1)
{
print("\n Result : " + matrix(a)(b));
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PeakPoint = new PeakPoint();
var matrix: Array[Array[Int]] = Array(
Array(10, 15, 11, 20),
Array(13, 16, 27, 25),
Array(11, 29, 28, 15),
Array(21, 13, 15, 14)
);
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}
}``````

#### Output

`` Result : 29``
``````import Foundation;
/*
Swift 4 Program for
Find a peak element in matrix
*/
class PeakPoint
{
func isSafe(_ matrix: [[Int]], _ i: Int, _ j: Int,
_ row: Int, _ col: Int) -> Bool
{
// 4 neighbors
// top bottom left and right
if (i - 1 >= 0)
{
// Top element
if (matrix[i - 1][j] > matrix[i][j])
{
return false;
}
}
if (i + 1 < row)
{
// Bottom element
if (matrix[i + 1][j] > matrix[i][j])
{
return false;
}
}
if (j - 1 >= 0)
{
// Left element
if (matrix[i][j - 1] > matrix[i][j])
{
return false;
}
}
if (j + 1 < col)
{
// Right element
if (matrix[i][j + 1] > matrix[i][j])
{
return false;
}
}
return true;
}
func findPeakPoint(_ matrix: [
[Int]
])
{
var a: Int = -1;
var b: Int = -1;
let row: Int = matrix.count;
let col: Int = matrix[0].count;
var i: Int = 0;
// Row
while (i < row && a == -1 && b == -1)
{
var j: Int = 0;
// Col
while (j < col && a == -1 && b == -1)
{
if (self.isSafe(matrix, i, j, row, col))
{
a = i;
b = j;
}
j += 1;
}
i += 1;
}
if (a  != -1 && b  != -1)
{
print("\n Result : ", matrix[a][b], terminator: "");
}
}
}
func main()
{
let matrix: [
[Int]
] = [
[10, 15, 11, 20],
[13, 16, 27, 25],
[11, 29, 28, 15],
[21, 13, 15, 14]
];
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}
main();``````

#### Output

`` Result :  29``
``````/*
Kotlin Program for
Find a peak element in matrix
*/
class PeakPoint
{
fun isSafe(matrix: Array < Array < Int >> ,
i: Int, j: Int, row: Int, col: Int): Boolean
{
// 4 neighbors
// top bottom left and right
if (i - 1 >= 0)
{
// Top element
if (matrix[i - 1][j] > matrix[i][j])
{
return false;
}
}
if (i + 1 < row)
{
// Bottom element
if (matrix[i + 1][j] > matrix[i][j])
{
return false;
}
}
if (j - 1 >= 0)
{
// Left element
if (matrix[i][j - 1] > matrix[i][j])
{
return false;
}
}
if (j + 1 < col)
{
// Right element
if (matrix[i][j + 1] > matrix[i][j])
{
return false;
}
}
return true;
}
fun findPeakPoint(matrix: Array < Array < Int >> ): Unit
{
var a: Int = -1;
var b: Int = -1;
val row: Int = matrix.count();
val col: Int = matrix[0].count();
var i: Int = 0;
// Row
while (i < row && a == -1 && b == -1)
{
var j: Int = 0;
// Col
while (j < col && a == -1 && b == -1)
{
if (this.isSafe(matrix, i, j, row, col))
{
a = i;
b = j;
}
j += 1;
}
i += 1;
}
if (a != -1 && b != -1)
{
print("\n Result : " + matrix[a][b]);
}
}
}
fun main(args: Array < String > ): Unit
{
val matrix: Array < Array < Int >> = arrayOf(
arrayOf(10, 15, 11, 20),
arrayOf(13, 16, 27, 25),
arrayOf(11, 29, 28, 15),
arrayOf(21, 13, 15, 14)
);
/*
13     27
↖  ↗
29
↙  ↘
21    15
------------
29 is peak
*/
}``````

#### Output

`` Result : 29``

## Time Complexity

The time complexity of the mentioned solution is O(N^2), where N is the number of rows or columns in the matrix. The `peakPoint` function iterates through each element in the matrix, and for each element, it performs constant-time operations (checking adjacent elements). Therefore, the overall time complexity is O(N^2).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.