Wednesday, May 4, 2022

Question 27 : Find peak element in the array

We need to print all the leaders present in the array. Element is the leader if it is greater than right side of elements.
For example::

``````arr[]={14, 12, 70, 15, 99, 65, 21, 90}
Here 99 and 90 are leader elements``````

Solution:

Solution 1:

Use two loops. Outer loop to iterate over array elements and inner loop to check for right elements of the array.

If the current element is greater than the right element then it is a leader.

Java code::
``````public static void findLeadersInAnArrayBruteForce(int arr[])
{
System.out.println("Finding leaders in an array using brute force : ");
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr[i] <= arr[j])
{
break;
}
}
System.out.print(arr[i]+" ");
}
}
``````

Time complexity : o(N^2)

Solution 2:

Lets find more optimized solution
We will use property that rightmost element is always a leader.

• We will start from rightmost element and track max.
• Whenever we get new max, that element is a leader.

Java code::

``````public static void findLeadersInAnArray(int arr[])
{
System.out.println("Finding leaders in an array : ");
int rightMax=arr[arr.length-1];
// Rightmost will always be a leader
System.out.print(rightMax+" ");
for (int i = arr.length-2; i>=0; i--) {
if(arr[i] > rightMax)
{
rightMax=arr[i];
System.out.print(" "+rightMax);
}
}
}``````

Time complexity : o(N)

Java Program to find leaders in the array::

``````public class FindLeadersInArrayMain {

public static void main(String[] args) {
int arr[]={14, 12, 70, 15, 99, 65, 21, 90};
System.out.println("n==================");
}

{
System.out.println("Finding leaders in an array using brute force : ");
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr[i] <= arr[j])
{
break;
}
}
System.out.print(arr[i]+" ");
}
}

{
System.out.println("Finding leaders in an array : ");
int rightMax=arr[arr.length-1];
// Rightmost will always be a leader
System.out.print(rightMax+" ");
for (int i = arr.length-2; i>=0; i--) {
if(arr[i] > rightMax)
{
rightMax=arr[i];
System.out.print(" "+rightMax);
}
}
}

}
``````
When you run the above program, you will get the below output::

``````Finding leaders in an array using brute force
99 90
==================
Finding leaders in an array :
90  99``````

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.