In this example, we’ll find leaders in an array.
An element of an array is a leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.
Input:
int[] arr1 = { 9, 178, 40, 3, 5, 2 };
Output:
[2, 5, 40, 178]
1. Java
Solution with time complexity O(n2)
public class LeadersInArray {
public static void main(String[] args) {
int[] arr = {9, 17, 40, 3, 50, 2};
List<Integer> leaders = findLeaders(arr);
System.out.println(leaders);
}
static List<Integer> findLeaders(int arr[]) {
List<Integer> leaders = new ArrayList();
for (int i = 0; i < arr.length - 1; i++) {
boolean isLeader = true;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[i]) {
isLeader = false;
break;
}
}
if (isLeader) {
leaders.add(arr[i]);
}
}
leaders.add(arr[arr.length - 1]);
return leaders;
}
}
Output:
[2, 50]
Solution with time complexity O(n)
public class LeadersInArray {
public static void main(String[] args) {
int[] arr = {19, 56, 23, 3, 55, 2};
List<Integer> leaders = leaders1(arr);
System.out.println(leaders);
}
static List<Integer> leaders1(int arr[]) {
List<Integer> leaders = new ArrayList();
int leaderFromRight = arr[arr.length - 1];
leaders.add(leaderFromRight);
for (int i = arr.length - 2; i >= 0; i--) {
if (arr[i] >= leaderFromRight) {
leaderFromRight = arr[i];
leaders.add(leaderFromRight);
}
}
return leaders;
}
}
Output:
[2, 55, 56]
Complete Java Solutions can be found here: Github Link