Question 28 : Find leaders in an 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 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++) {
         boolean isLeader=true;
         for (int j = i+1; j < arr.length; j++) {
             if(arr[i] <= arr[j])
             { 
                 isLeader=false;
                 break;
             } 
      }
     if(isLeader)
         System.out.print(arr[i]+" ");
     }
 }

Time complexity : o(N^2)

Solution 2:

Let's find more optimized solution
We will use the property that the rightmost element is always a leader.

• We will start from the rightmost element and track max.
• Whenever we get the 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};
  findLeadersInAnArrayBruteForce(arr);
  System.out.println("n==================");
  findLeadersInAnArray(arr);
 }
 
 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++) {
   boolean isLeader=true;
   for (int j = i+1; j < arr.length; j++) {
    if(arr[i] <= arr[j])
    { 
     isLeader=false;
     break;
    }    
   }
   if(isLeader)
    System.out.print(arr[i]+" ");
  }
 }
 
 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);
   }
  }
 }
 
}

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.                            

   

Share This

• Facebook
• Twitter
• Linkedin
• Pinterest