Find leaders in an array

Problem:

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 current element is greater than right elements than 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:

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:

package org.arpit.java2blog;

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 above program, you will get below output:
Finding leaders in an array using brute force
99 90 
==================
Finding leaders in an array : 
90  99

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012