Leaders in an array

Leaders in the array referees to the elements which are strictly greater than the elements present on the right-hand side of the array elements

For example in the given array [16, 17, 4, 3, 5, 2], the leaders are 17, 5, and 2.

There are various ways to find the leaders in the array some of them are as follows

1. Brute force:- This method involves comparing each element of the array to the right-hand side of the element and finding if it is strictly greater than the element. The worst-case time complexity will be O(n²)

def find_leaders(arr):
    n = len(arr)
    leaders = []
    for i in range(n):
        is_leader = True
        for j in range(i+1, n):
            if arr[i] < arr[j]:
                is_leader = False
                break
        if is_leader:
            leaders.append(arr[i])
    return leaders

1. Iterating the elements from the last:- This problem can be solved by tracing the elements from the last and comparing it with the global max seen so far

def find_leaders(arr):
    n = len(arr)
    leaders = []
    max_so_far = float('-inf')
    for i in range(n-1,-1,-1):
        if arr[i]>max_so_far:
            max_so_far = arr[i]
            leaders.append(max_so_far)
            
    
    return leaders[::-1]
    

1. First, we define a function find_leaders that takes an array arr as input.
2. We initialize a variable n to the length of the array, and create an empty list leaders to store the leaders in the array.
3. We also initialize a variable max_so_far to negative infinity. This variable will keep track of the maximum element seen so far while iterating the array.
4. We start iterating the array from the last element to the first element using a for loop with a step of -1. For each element in the array, we check if it is greater than max_so_far.
5. If the current element is greater than max_so_far, we update max_so_far to the current element and append it to the leaders list.
6. Finally, we return the leaders list in reverse order, as we appended the leaders to the list while iterating the array from the last element to the first element.