Problem

Given an integer array, find all the leader elements in the array.

Definition

An element is said to be a leader if all the elements on its right side are smaller than it. The rightmost element is always a leader.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: arr = [14, 9, 11, 7, 8, 5, 3]
Output: [14, 11, 8, 5, 3]
Explanation: 
14 is a leader because there are no elements to its right that are greater than 14.
11 is a leader because all elements to its right (7, 8, 5, 3) are smaller than 11.
8 is a leader because all elements to its right (5, 3) are smaller than 8.
5 is a leader because the element to its right (3) is smaller than 5.
3 is a leader because it is the rightmost element.

Example 2:

1
2
3
4
5
6

Input: arr = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Explanation: 
17 is a leader because all elements to its right (4, 3, 5, 2) are smaller than 17.
5 is a leader because the elements to its right (2) are smaller than 5.
2 is a leader because it is the rightmost element.

Solution

Method 1 - Iterate from right to left

Here is the approach:

  1. Traverse the array from right to left.
  2. Keep track of the maximum element seen so far.
  3. If the current element is greater than or equal to the maximum element, mark it as a leader.
  4. The rightmost element is always a leader.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public static List<Integer> findLeaders(int[] arr) {
        int n = arr.length;
        List<Integer> leaders = new ArrayList<>();
        int maxFromRight = arr[n - 1];

        // The rightmost element is always a leader
        leaders.add(maxFromRight);

        // Traverse the array from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] >= maxFromRight) {
                leaders.add(arr[i]);
                maxFromRight = arr[i];
            }
        }

        // Reverse to maintain the order as in the original array
        Collections.reverse(leaders);
        return leaders;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def find_leaders(arr):
    n = len(arr)
    leaders = []
    max_from_right = arr[-1]

    # The rightmost element is always a leader
    leaders.append(max_from_right)

    # Traverse the array from right to left
    for i in range(n - 2, -1, -1):
        if arr[i] >= max_from_right:
            leaders.append(arr[i])
            max_from_right = arr[i]

    # Reverse to maintain the order as in the original array
    leaders.reverse()
    return leaders


# Example usage:
arr1 = [14, 9, 11, 7, 8, 5, 3]
print(find_leaders(arr1))  # Output: [14, 11, 8, 5, 3]

arr2 = [16, 17, 4, 3, 5, 2]
print(find_leaders(arr2))  # Output: [17, 5, 2]

Complexity

  • ⏰ Time complexity: O(n), due to a single traversal of the array.
  • 🧺 Space complexity: O(n), for storing the leader elements.