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