Find peak element in array

The problem of finding peak elements in an array involves identifying elements that are greater than or equal to their neighboring elements. A peak element stands out as a point where the values increase until that point and then start decreasing. This article explores the intricacies of solving the peak element problem, provides an approach to tackle it, presents the algorithm's details, and explains its time complexity.

Problem Statement

Given an array of integers, the task is to find and display all the peak elements in the array.

Example

Consider the array [4, 2, 7, 10, 2, 19, 21]. The peak elements in this array are 4, 10, and 21.

A peak element in this context is an element that is greater than or equal to its neighboring elements. Let's analyze the elements one by one:

1. 4: The element 4 has neighbors 2 on the left and 2 on the right. It's greater than both, making it a peak element.
2. 2: The element 2 has neighbors 4 on the right. It's not greater than any of its neighbors, so it's not a peak element.
3. 7: The element 7 has neighbors 2 on the left and 10 on the right. It's greater than both, making it a peak element.
4. 10: The element 10 has neighbors 7 on the left and 2 on the right. It's greater than both, making it a peak element.
5. 2: The element 2 has neighbors 10 on the left and 19 on the right. It's not greater than any of its neighbors, so it's not a peak element.
6. 19: The element 19 has neighbors 2 on the left and 21 on the right. It's not greater than any of its neighbors, so it's not a peak element.
7. 21: The element 21 has neighbor 19 on the left. It's greater than its neighbor, making it a peak element.

Idea to Solve the Problem

To solve this problem, we need to examine each element in the array and determine whether it is a peak element. This can be done by comparing the element with its neighboring elements.

Pseudocode

peak_elements(arr, size):
    if size < 2:
        return
    
    for i in range(size):
        if i == 0 and i + 1 < size and arr[i] > arr[i + 1]:
            print("Index:", i)
        elif i == size - 1 and i > 0 and arr[i] > arr[i - 1]:
            print("Index:", i)
        elif i > 0 and i + 1 < size and arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
            print("Index:", i)
    
    if no peak element is found:
        print("Not Exist")

Algorithm Explanation

1. Check if the array size is less than 2. If so, return, as there can't be any peak elements in an array of size 1 or 0.
2. Iterate through the array using a loop with index i.
3. For each i, perform the following checks:
   • If i is the first element and it is greater than the next element, print its index.
   • If i is the last element and it is greater than the previous element, print its index.
   • If i is an intermediate element and it is greater than both its previous and next elements, print its index.
4. If no peak element is found (status remains 0), print "Not Exist."

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// C Program 
// Find peak element in array
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
//Determine of all peak points in an given array
void peak_elements(int arr[], int size)
{
	if (size < 2)
	{
		return;
	}
	//Display array elements
	printf("\n\n Arrays : ");
	display(arr, size);
	int status = 0;
	printf(" Peak point  : ");
	//Iterating array elements
	for (int i = 0; i < size; ++i)
	{
		//There are three test cases are follows in peak element
		//Case 1 : When first element is peak element
		//Case 2 : When last element is peak element
		//Case 3 : When intermediate element is peak element 
		//Check first element is peak element or not
		if (i == 0 && i + 1 < size && arr[i] > arr[i + 1])
		{
			printf("\n Index : %d", i);
			status = 1;
		}
		else if (i == size - 1 && i > 0 && arr[i] > arr[i - 1])
		{
			//When last element is peak element
			printf("\n Index : %d", i);
			status = 1;
		}
		else if (i > 0 && i + 1 < size && arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
		{
			//When intermediate element is peak element
			printf("\n Index : %d", i);
			status = 1;
		}
	}
	if (status == 0)
	{
		printf(" Not Exist \n");
	}
}
int main()
{
	int arr1[] = {
		2 , 3 , 1 , 6 , 4
	};
	//Get the size of array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	peak_elements(arr1, size);
	int arr2[] = {
		4 , 2 , 7 , 10 , 2 , 19 , 21
	};
	//Get the size of array
	size = sizeof(arr2) / sizeof(arr2[0]);
	peak_elements(arr2, size);
	return 0;
}

 Arrays : 2 3 1 6 4
 Peak point  :
 Index : 1
 Index : 3

 Arrays : 4 2 7 10 2 19 21
 Peak point  :
 Index : 0
 Index : 3
 Index : 6

// Java Program
// Find peak element in array
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	//Determine of all peak points in an given array
	public void peak_elements(int[] arr, int size)
	{
		if (size < 2)
		{
			return;
		}
		System.out.print("\n\n Arrays : ");
		display(arr, size);
		int status = 0;
		System.out.print(" Peak point : ");
		//Iterating array elements
		for (int i = 0; i < size; ++i)
		{
			//There are three test cases are follows in peak element
			//Case 1 : When first element is peak element
			//Case 2 : When last element is peak element
			//Case 3 : When intermediate element is peak element 
          
			//Check first element is peak element or not
			if (i == 0 && i + 1 < size && arr[i] > arr[i + 1])
			{
				System.out.print("\n Index : " + i + "");
				status = 1;
			}
			else if (i == size - 1 && i > 0 && arr[i] > arr[i - 1])
			{
				System.out.print("\n Index : " + i + "");
				status = 1;
			}
			else if (i > 0 && i + 1 < size && arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
			{
				System.out.print("\n Index : " + i + "");
				status = 1;
			}
		}
		if (status == 0)
		{
			System.out.print(" Not Exist \n");
		}
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		int arr1[] = {
			2,
			3,
			1,
			6,
			4
		};
		//Get the size of array
		int size = arr1.length;
		obj.peak_elements(arr1, size);
		int arr2[] = {
			4,
			2,
			7,
			10,
			2,
			19,
			21
		};
		//Get the size of array
		size = arr2.length;
		obj.peak_elements(arr2, size);
	}
}

 Arrays :  2 3 1 6 4
 Peak point :
 Index : 1
 Index : 3

 Arrays :  4 2 7 10 2 19 21
 Peak point :
 Index : 0
 Index : 3
 Index : 6

//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find peak element in array
class MyArray
{
	public:
		//Function which is display array elements
		void display(int arr[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	//Determine of all peak points in an given array
	void peak_elements(int arr[], int size)
	{
		if (size < 2)
		{
			return;
		}
		cout << "\n\n Arrays : ";
		this->display(arr, size);
		int status = 0;
		cout << " Peak point : ";
		//Iterating array elements
		for (int i = 0; i < size; ++i)
		{
			//There are three test cases are follows in peak element
			//Case 1 : When first element is peak element
			//Case 2 : When last element is peak element
			//Case 3 : When intermediate element is peak element 
			//Check first element is peak element or not
			if (i == 0 && i + 1 < size && arr[i] > arr[i + 1])
			{
				cout << "\n Index : " << i << "";
				status = 1;
			}
			else if (i == size - 1 && i > 0 && arr[i] > arr[i - 1])
			{
				cout << "\n Index : " << i << "";
				status = 1;
			}
			else if (i > 0 && i + 1 < size && arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
			{
				cout << "\n Index : " << i << "";
				status = 1;
			}
		}
		if (status == 0)
		{
			cout << " Not Exist \n";
		}
	}
};
int main()
{
	MyArray obj = MyArray();
	int arr1[] = {
		2 , 3 , 1 , 6 , 4
	};
	//Get the size of array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	obj.peak_elements(arr1, size);
	int arr2[] = {
		4 , 2 , 7 , 10 , 2 , 19 , 21
	};
	//Get the size of array
	size = sizeof(arr2) / sizeof(arr2[0]);
	obj.peak_elements(arr2, size);
	return 0;
}

 Arrays :  2 3 1 6 4
 Peak point :
 Index : 1
 Index : 3

 Arrays :  4 2 7 10 2 19 21
 Peak point :
 Index : 0
 Index : 3
 Index : 6

//Include namespace system
using System;
// C# Program
// Find peak element in array
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	//Determine of all peak points in an given array
	public void peak_elements(int[] arr, int size)
	{
		if (size < 2)
		{
			return;
		}
		Console.Write("\n\n Arrays : ");
		display(arr, size);
		int status = 0;
		Console.Write(" Peak point : ");
		//Iterating array elements
		for (int i = 0; i < size; ++i)
		{
			//There are three test cases are follows in peak element
			//Case 1 : When first element is peak element
			//Case 2 : When last element is peak element
			//Case 3 : When intermediate element is peak element 
			//Check first element is peak element or not
			if (i == 0 && i + 1 < size && arr[i] > arr[i + 1])
			{
				Console.Write("\n Index : " + i + "");
				status = 1;
			}
			else if (i == size - 1 && i > 0 && arr[i] > arr[i - 1])
			{
				Console.Write("\n Index : " + i + "");
				status = 1;
			}
			else if (i > 0 && i + 1 < size && arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
			{
				Console.Write("\n Index : " + i + "");
				status = 1;
			}
		}
		if (status == 0)
		{
			Console.Write(" Not Exist \n");
		}
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr1 = {
			2 , 3 , 1 , 6 , 4
		};
		//Get the size of array
		int size = arr1.Length;
		obj.peak_elements(arr1, size);
		int[] arr2 = {
			4 , 2 , 7 , 10 , 2 , 19 , 21
		};
		//Get the size of array
		size = arr2.Length;
		obj.peak_elements(arr2, size);
	}
}

 Arrays :  2 3 1 6 4
 Peak point :
 Index : 1
 Index : 3

 Arrays :  4 2 7 10 2 19 21
 Peak point :
 Index : 0
 Index : 3
 Index : 6

<?php
// Php Program
// Find peak element in array
class MyArray
{
	//Function which is display array elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	//Determine of all peak points in an given array
	public	function peak_elements($arr, $size)
	{
		if ($size < 2)
		{
			return;
		}
		echo "\n\n Arrays : ";
		$this->display($arr, $size);
		$status = 0;
		echo " Peak point : ";
		//Iterating array elements
		for ($i = 0; $i < $size; ++$i)
		{
			//There are three test cases are follows in peak element
			//Case 1 : When first element is peak element
			//Case 2 : When last element is peak element
			//Case 3 : When intermediate element is peak element 
			//Check first element is peak element or not
			if ($i == 0 && $i + 1 < $size && $arr[$i] > $arr[$i + 1])
			{
				echo "\n Index : ". $i ."";
				$status = 1;
			}
			else if ($i == $size - 1 && $i > 0 && $arr[$i] > $arr[$i - 1])
			{
				echo "\n Index : ". $i ."";
				$status = 1;
			}
			else if ($i > 0 && $i + 1 < $size && $arr[$i] > $arr[$i - 1] && $arr[$i] > $arr[$i + 1])
			{
				echo "\n Index : ". $i ."";
				$status = 1;
			}
		}
		if ($status == 0)
		{
			echo " Not Exist \n";
		}
	}
}

function main()
{
	$obj = new MyArray();
	$arr1 = array(2, 3, 1, 6, 4);
	//Get the size of array
	$size = count($arr1);
	$obj->peak_elements($arr1, $size);
	$arr2 = array(4, 2, 7, 10, 2, 19, 21);
	//Get the size of array
	$size = count($arr2);
	$obj->peak_elements($arr2, $size);
}
main();

 Arrays :  2 3 1 6 4
 Peak point :
 Index : 1
 Index : 3

 Arrays :  4 2 7 10 2 19 21
 Peak point :
 Index : 0
 Index : 3
 Index : 6

// Node Js Program
// Find peak element in array
class MyArray
{
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	//Determine of all peak points in an given array
	peak_elements(arr, size)
	{
		if (size < 2)
		{
			return;
		}
		process.stdout.write("\n\n Arrays : ");
		this.display(arr, size);
		var status = 0;
		process.stdout.write(" Peak point : ");
		//Iterating array elements
		for (var i = 0; i < size; ++i)
		{
			//There are three test cases are follows in peak element
			//Case 1 : When first element is peak element
			//Case 2 : When last element is peak element
			//Case 3 : When intermediate element is peak element 
			//Check first element is peak element or not
			if (i == 0 && i + 1 < size && arr[i] > arr[i + 1])
			{
				process.stdout.write("\n Index : " + i + "");
				status = 1;
			}
			else if (i == size - 1 && i > 0 && arr[i] > arr[i - 1])
			{
				process.stdout.write("\n Index : " + i + "");
				status = 1;
			}
			else if (i > 0 && i + 1 < size && arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
			{
				process.stdout.write("\n Index : " + i + "");
				status = 1;
			}
		}
		if (status == 0)
		{
			process.stdout.write(" Not Exist \n");
		}
	}
}

function main()
{
	var obj = new MyArray();
	var arr1 = [2, 3, 1, 6, 4];
	//Get the size of array
	var size = arr1.length;
	obj.peak_elements(arr1, size);
	var arr2 = [4, 2, 7, 10, 2, 19, 21];
	//Get the size of array
	size = arr2.length;
	obj.peak_elements(arr2, size);
}
main();

 Arrays :  2 3 1 6 4
 Peak point :
 Index : 1
 Index : 3

 Arrays :  4 2 7 10 2 19 21
 Peak point :
 Index : 0
 Index : 3
 Index : 6

#  Python 3 Program
#  Find peak element in array
class MyArray :
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(arr[i], end = " ")
			i += 1
		
		print(end = "\n")
	
	# Determine of all peak points in an given array
	def peak_elements(self, arr, size) :
		if (size < 2) :
			return
		
		print("\n Arrays : ", end = "")
		self.display(arr, size)
		status = 0
		print(" Peak point : ")
		# Iterating array elements
		i = 0
		while (i < size) :
			# There are three test cases are follows in peak element
			# Case 1 : When first element is peak element
			# Case 2 : When last element is peak element
			# Case 3 : When intermediate element is peak element 
			# Check first element is peak element or not
			if (i == 0 and i + 1 < size and arr[i] > arr[i + 1]) :
				print(" Index : ", i )
				status = 1
			
			elif(i == size - 1 and i > 0 and arr[i] > arr[i - 1]) :
				print(" Index : ", i , end = "")
				status = 1
			
			elif(i > 0 and i + 1 < size and arr[i] > arr[i - 1] and arr[i] > arr[i + 1]) :
				print(" Index : ", i )
				status = 1
			
			i += 1
		
		if (status == 0) :
			print(" Not Exist ")
		
	

def main() :
	obj = MyArray()
	arr1 = [2, 3, 1, 6, 4]
	# Get the size of array
	size = len(arr1)
	obj.peak_elements(arr1, size)
	arr2 = [4, 2, 7, 10, 2, 19, 21]
	# Get the size of array
	size = len(arr2)
	obj.peak_elements(arr2, size)

if __name__ == "__main__": main()

 Arrays : 2 3 1 6 4
 Peak point :
 Index :  1
 Index :  3

 Arrays : 4 2 7 10 2 19 21
 Peak point :
 Index :  0
 Index :  3
 Index :  6

#  Ruby Program
#  Find peak element in array
class MyArray

	# Function which is display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	# Determine of all peak points in an given array
	def peak_elements(arr, size)
	
		if (size < 2)
		
			return
		end
		print("\n\n Arrays : ")
		self.display(arr, size)
		status = 0
		print(" Peak point : ")
		# Iterating array elements
		i = 0
		while (i < size)
		
			# There are three test cases are follows in peak element
			# Case 1 : When first element is peak element
			# Case 2 : When last element is peak element
			# Case 3 : When intermediate element is peak element 
			# Check first element is peak element or not
			if (i == 0 && i + 1 < size && arr[i] > arr[i + 1])
			
				print("\n Index : ", i)
				status = 1
			elsif(i == size - 1 && i > 0 && arr[i] > arr[i - 1])
			
				print("\n Index : ", i)
				status = 1
			elsif(i > 0 && i + 1 < size && arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
			
				print("\n Index : ", i)
				status = 1
			end
			i += 1
		end
		if (status == 0)
		
			print(" Not Exist \n")
		end
	end
end
def main()

	obj = MyArray.new()
	arr1 = [2, 3, 1, 6, 4]
	# Get the size of array
	size = arr1.length
	obj.peak_elements(arr1, size)
	arr2 = [4, 2, 7, 10, 2, 19, 21]
	# Get the size of array
	size = arr2.length
	obj.peak_elements(arr2, size)
end
main()

 Arrays :  2 3 1 6 4
 Peak point : 
 Index : 1
 Index : 3

 Arrays :  4 2 7 10 2 19 21
 Peak point : 
 Index : 0
 Index : 3
 Index : 6

// Scala Program
// Find peak element in array
class MyArray
{
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	//Determine of all peak points in an given array
	def peak_elements(arr: Array[Int], size: Int): Unit = {
		if (size < 2)
		{
			return;
		}
		print("\n\n Arrays : ");
		display(arr, size);
		var status: Int = 0;
		print(" Peak point : ");
		//Iterating array elements
		var i: Int = 0;
		while (i < size)
		{
			//There are three test cases are follows in peak element
			//Case 1 : When first element is peak element
			//Case 2 : When last element is peak element
			//Case 3 : When intermediate element is peak element 
			//Check first element is peak element or not
			if (i == 0 && i + 1 < size && arr(i) > arr(i + 1))
			{
				print("\n Index : " + i);
				status = 1;
			}
			else if (i == size - 1 && i > 0 && arr(i) > arr(i - 1))
			{
				print("\n Index : " + i);
				status = 1;
			}
			else if (i > 0 && i + 1 < size && arr(i) > arr(i - 1) && arr(i) > arr(i + 1))
			{
				print("\n Index : " + i);
				status = 1;
			}
			i += 1;
		}
		if (status == 0)
		{
			print(" Not Exist \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		var arr1: Array[Int] = Array(2, 3, 1, 6, 4);
		//Get the size of array
		var size: Int = arr1.length;
		obj.peak_elements(arr1, size);
		var arr2: Array[Int] = Array(4, 2, 7, 10, 2, 19, 21);
		//Get the size of array
		size = arr2.length;
		obj.peak_elements(arr2, size);
	}
}

 Arrays :  2 3 1 6 4
 Peak point :
 Index : 1
 Index : 3

 Arrays :  4 2 7 10 2 19 21
 Peak point :
 Index : 0
 Index : 3
 Index : 6

// Swift Program
// Find peak element in array
class MyArray
{
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Determine of all peak points in an given array
	func peak_elements(_ arr: [Int], _ size: Int)
	{
		if (size < 2)
		{
			return;
		}
		print("\n\n Arrays : ", terminator: "");
		self.display(arr, size);
		var status: Int = 0;
		print(" Peak point : ", terminator: "");
		//Iterating array elements
		var i: Int = 0;
		while (i < size)
		{
			//There are three test cases are follows in peak element
			//Case 1 : When first element is peak element
			//Case 2 : When last element is peak element
			//Case 3 : When intermediate element is peak element 
			//Check first element is peak element or not
			if (i == 0 && i + 1 < size && arr[i] > arr[i + 1])
			{
				print("\n Index : ", i, terminator: "");
				status = 1;
			}
			else if (i == size - 1 && i > 0 && arr[i] > arr[i - 1])
			{
				print("\n Index : ", i, terminator: "");
				status = 1;
			}
			else if (i > 0 && i + 1 < size && arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
			{
				print("\n Index : ", i, terminator: "");
				status = 1;
			}
			i += 1;
		}
		if (status == 0)
		{
			print(" Not Exist \n", terminator: "");
		}
	}
}
func main()
{
	let obj: MyArray = MyArray();
	let arr1: [Int] = [2, 3, 1, 6, 4];
	//Get the size of array
	var size: Int = arr1.count;
	obj.peak_elements(arr1, size);
	let arr2: [Int] = [4, 2, 7, 10, 2, 19, 21];
	//Get the size of array
	size = arr2.count;
	obj.peak_elements(arr2, size);
}
main();

 Arrays :   2  3  1  6  4
 Peak point :
 Index :  1
 Index :  3

 Arrays :   4  2  7  10  2  19  21
 Peak point :
 Index :  0
 Index :  3
 Index :  6

Time Complexity Analysis

The algorithm iterates through the array once. In each iteration, constant-time comparisons are made. Therefore, the time complexity is O(n), where n is the size of the array. This linear time complexity indicates that the algorithm's efficiency scales well with the size of the array.