Python Program to Find Leaders in Array

A leader in an array is an element greater than all elements to its right; use a loop from right to left, track the maximum, and collect elements greater than this max with code like for i in reversed(range(len(arr))): if arr[i] > max_from_right: leaders.append(arr[i]).

Examples

Input[16, 17, 4, 3, 5, 2]

Output[17, 5, 2]

Input[1, 2, 3, 4, 0]

Output[4, 0]

Input[7, 10, 4, 10, 6, 5, 2]

Output[10, 10, 6, 5, 2]

How to Think About It

To find leaders, start from the right end of the array because the rightmost element is always a leader. Keep track of the maximum value seen so far. Move leftwards, and whenever you find an element greater than this maximum, it is a leader. Update the maximum and continue until the start of the array.

Algorithm

1

Initialize an empty list to store leaders.

2

Set the maximum from the right as the last element of the array.

3

Add the last element to the leaders list.

4

Traverse the array from second last element to the first.

5

For each element, if it is greater than the current maximum, add it to leaders and update the maximum.

6

Reverse the leaders list to maintain the original order and return it.

Code

python

def find_leaders(arr):
    leaders = []
    max_from_right = arr[-1]
    leaders.append(max_from_right)
    for i in range(len(arr) - 2, -1, -1):
        if arr[i] >= max_from_right:
            max_from_right = arr[i]
            leaders.append(max_from_right)
    leaders.reverse()
    return leaders

# Example usage
arr = [16, 17, 4, 3, 5, 2]
print(find_leaders(arr))

Output

[17, 5, 2]

Dry Run

Let's trace the array [16, 17, 4, 3, 5, 2] through the code

1

Initialize

leaders = [], max_from_right = 2, leaders = [2]

2

Check element 5

5 >= 2, update max_from_right = 5, leaders = [2, 5]

3

Check element 3

3 >= 5? No, skip

4

Check element 4

4 >= 5? No, skip

5

Check element 17

17 >= 5, update max_from_right = 17, leaders = [2, 5, 17]

6

Check element 16

16 >= 17? No, skip

7

Reverse leaders

leaders = [17, 5, 2]

Element	max_from_right	Leaders List
2	2	[2]
5	5	[2, 5]
3	5	[2, 5]
4	5	[2, 5]
17	17	[2, 5, 17]
16	17	[2, 5, 17]

Why This Works

Step 1: Start from the right

The rightmost element is always a leader because no elements are to its right.

Step 2: Track maximum from right

Keep updating the maximum value seen from the right to compare with other elements.

Step 3: Add leaders when found

If an element is greater than or equal to the current maximum, it is a leader and added to the list.

Step 4: Reverse the list

Since we traverse from right to left, reverse the collected leaders to restore original order.

Alternative Approaches

Using stack

python

def find_leaders_stack(arr):
    stack = []
    for num in reversed(arr):
        while stack and stack[-1] < num:
            stack.pop()
        stack.append(num)
    return list(reversed(stack))

print(find_leaders_stack([16, 17, 4, 3, 5, 2]))

This method uses a stack to maintain leaders but is less straightforward and uses extra space.

Brute force

python

def find_leaders_brute(arr):
    leaders = []
    for i in range(len(arr)):
        if all(arr[i] > arr[j] for j in range(i+1, len(arr))):
            leaders.append(arr[i])
    return leaders

print(find_leaders_brute([16, 17, 4, 3, 5, 2]))

This checks each element against all to its right, simple but inefficient with O(n^2) time.

Complexity: O(n) time, O(k) space

Time Complexity

The program loops through the array once from right to left, so it runs in linear time O(n).

Space Complexity

Extra space is used to store leaders, which can be up to O(n) in the worst case if all elements are leaders.

Which Approach is Fastest?

The main approach is fastest with O(n) time, while brute force is slower at O(n^2). The stack method is also O(n) but uses more complex logic.

Approach	Time	Space	Best For
Right-to-left scan	O(n)	O(k)	Efficient and simple leader detection
Stack method	O(n)	O(n)	When stack operations are preferred
Brute force	O(n^2)	O(k)	Simple but inefficient for large arrays