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 14In 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:
- Define a function
isSafeto check if a given element is a peak by comparing it with its adjacent elements. - Define a function
peakPointto 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 theisSafefunction. c. If a peak element is found, print it. - In the
mainfunction, create a matrix and call thepeakPointfunction 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)
{
PeakPoint task = new PeakPoint();
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
*/
task.findPeakPoint(matrix);
}
}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()
{
PeakPoint *task = new PeakPoint();
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
*/
task->findPeakPoint(matrix);
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)
{
PeakPoint task = new PeakPoint();
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
*/
task.findPeakPoint(matrix);
}
}Output
Result : 29package 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
*/
task.findPeakPoint(matrix)
}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()
{
$task = new PeakPoint();
$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
*/
$task->findPeakPoint($matrix);
}
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 task = new PeakPoint();
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
*/
task.findPeakPoint(matrix);
}
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() :
task = PeakPoint()
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
task.findPeakPoint(matrix)
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()
task = PeakPoint.new()
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
task.findPeakPoint(matrix)
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
*/
task.findPeakPoint(matrix);
}
}Output
Result : 29import 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 task: PeakPoint = PeakPoint();
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
*/
task.findPeakPoint(matrix);
}
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 task: PeakPoint = PeakPoint();
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
*/
task.findPeakPoint(matrix);
}Output
Result : 29Time 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).
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.
New Comment