Data Structure & Algorithms
DSA
Array carry forword
Leaders in an Array

Leaders in an array

Problem Description

Given an integer array A containing N distinct integers, you have to find all the leaders in array A. An element is a leader if it is strictly greater than all the elements to its right side.

NOTE: The rightmost element is always a leader.

Problem Constraints

1 <= N <= 10^5
1 <= A[i] <= 10^8

Input Format

There is a single input argument which a integer array A

Output Format

Return an integer array denoting all the leader elements of the array.

Example Input

Input 1:
A = [16, 17, 4, 3, 5, 2]

Input 2:
A = [5, 4]

Example Output

Output 1:
[17, 2, 5]

Output 2:
[5, 4]

Example Explanation

Explanation 1:
Element 17 is strictly greater than all the elements on the right side to it.
Element 2 is strictly greater than all the elements on the right side to it.
Element 5 is strictly greater than all the elements on the right side to it.
So we will return these three elements i.e [17, 2, 5], we can also return [2, 5, 17] or [5, 2, 17] or any other ordering.

Explanation 2:
Element 5 is strictly greater than all the elements on the right side to it.
Element 4 is strictly greater than all the elements on the right side to it.
So we will return these two elements i.e [5, 4], we can also any other ordering.

Output

Java
import java.util.ArrayList;
import java.util.List;
 
public class LeadersInArray {
    public List<Integer> findLeaders(int[] A) {
        List<Integer> leaders = new ArrayList<>();
        if (A.length == 0) return leaders;
        
        int maxFromRight = A[A.length - 1];
        leaders.add(maxFromRight);
        
        for (int i = A.length - 2; i >= 0; i--) {
            if (A[i] > maxFromRight) {
                maxFromRight = A[i];
                leaders.add(maxFromRight);
            }
        }
        
        Collections.reverse(leaders); // Reversing to get the original order
        return leaders;
    }
}
Python
def find_leaders(A):
    leaders = []
    if not A:
        return leaders
 
    max_from_right = A[-1]
    leaders.append(max_from_right)
 
    for i in range(len(A) - 2, -1, -1):
        if A[i] > max_from_right:
            max_from_right = A[i]
            leaders.append(max_from_right)
 
    return leaders[::-1]  # Reversing to get the original order
JavaScript
function findLeaders(A) {
    let leaders = [];
    if (A.length === 0) return leaders;
 
    let maxFromRight = A[A.length - 1];
    leaders.push(maxFromRight);
 
    for (let i = A.length - 2; i >= 0; i--) {
        if (A[i] > maxFromRight) {
            maxFromRight = A[i];
            leaders.push(maxFromRight);
        }
    }
 
    return leaders.reverse(); // Reversing to get the original order
}