How to Find Leaders in an Array

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

The complete list can be found here: Practise Programming Questions