Wednesday, 12 August 2015

Find leaders in array

An element is leader if it is greater than all the elements to its right side. For example for the array {20, 5, 25, 17, 16, 19, 12, 13, 2, 1}
Leaders are {25, 19, 13, 2, 1}.


We can solve this problem by traversing from right side.
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class Leaders {

 public static List<Integer> getLeaders(int arr[]){
  Objects.nonNull(arr);
  LinkedList<Integer> leaders = new LinkedList<> ();
  
  if(arr.length < 2)
   return leaders;
  
  int length = arr.length-1;
  
  int leader = arr[length];
  leaders.push(leader);
  
  for(int i=length-1; i>-1; i--){
   if(arr[i] > leader){
    leader = arr[i];
    leaders.push(leader);
   }
  }
  
  return leaders;
 }
}


Following is the junit test case for above program.
import static org.junit.Assert.assertTrue;

import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class LeadersTest {
 
 @Test
 public void test1(){
  int arr[] = {20, 5, 25, 17, 16, 19, 12, 13, 2, 1};
  List<Integer> actual = Leaders.getLeaders(arr);
  List<Integer> expected = Arrays.asList(25, 19, 13, 2, 1);
  
  assertTrue(actual.equals(expected));
 }

}



No comments:

Post a Comment