Program to print all the LEADERS in an array in Python

In this tutorial, we will learn how to find all the leaders in the array.

Leader— An element of an array is called a leader if there is no element greater than it to the right side of it.

The last element is always a leader in the array, as it does not have any element on the right side of it.

We can print the leaders in any order.

Examples:

• Input:  [2 , 3 , 20 , 15 , 8 , 3]

Output:  [20 , 15 , 8 , 3]

•  Input: [23 , 25 , 88 , 78]

Output: [88 , 78]

Brute force

Traverse through the entire element, and check if a number greater than the current number exists on the right side of it.

If a number greater than the current number does not exist, then the current number is a leader of the array.

Time Complexity-O(N^2)

arr = [2 , 3 , 20 , 15 , 8 , 3]

for i in range(0 , len(arr)):
    a=0
    for j in range(i+1 , len(arr)):
        if arr[j]>arr[i]:      #greater element on the right side exists
            a=1                #current element is not a leader
            break
    if a==0:
        print(arr[i])

OUTPUT:

20
15
8
3

Method 2-Leaders in an array

Initialize the max_so_far variable with -1.

We will traverse the array from the left side, and check for every element in the array.

If the current element is greater than the maximum element found so far, then it is a leader otherwise, it is not a leader.

Then we update the maximum element so far.

Time Complexity: O(N)

arr=[23 , 25 , 88 , 78]

max_so_far=-1

for i in range(len(arr)-1 , -1 , -1):
    if arr[i] >= max_so_far:
        print(arr[i])
    max_so_far=max(max_so_far , arr[i] )

OUTPUT:

78
88

You may also read:

Josephus problem and recursive solution in Python

Find the closest pair from two sorted arrays in Python