Leaders in an array

Given an array of integers, the task is to find all the leaders in the array.

An element of an array is considered a leader if it is greater than or equal to all elements to its right. The rightmost element is always a leader since there are no elements to its right.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Explanation: The leaders are 17, 5, and 2 because:
17 is greater than all elements to its right.
5 is greater than all elements to its right.
2 is the last element, so it's a leader.

Example 2:
Input:
arr = [1, 2, 3, 4, 0]
Output: [4, 0]
Explanation: The leaders are 4 and 0 because:
4 is greater than 0, and 0 is the last element.

Approach to find the leaders in an array

  1. Traverse the Array from Right to Left:
    • The key observation is that any element is a leader if it is greater than or equal to all the elements to its right.
    • Start by initializing the rightmost element as the current leader (since no elements are on its right).
    • Traverse the array from right to left and check if the current element is greater than or equal to the current leader. If it is, update the leader and add the current element to the list of leaders.
  2. Algorithm:
    • Initialize the last element as the leader.
    • Traverse the array from right to left, updating the leader if the current element is greater than or equal to the current leader.
    • Return the list of leaders, but reverse it since we collected the leaders from the rightmost side.

C++ Program to find the Leaders in an array

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find leaders in the array
vector<int> findLeaders(vector<int>& arr) {
    int n = arr.size();
    vector<int> leaders;

    // Initialize the rightmost element as the leader
    int currentLeader = arr[n - 1];
    leaders.push_back(currentLeader);

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

    // Reverse the leaders list since we traversed from right to left
    reverse(leaders.begin(), leaders.end());

    return leaders;
}

int main() {
    vector<int> arr = {16, 17, 4, 3, 5, 2};
    vector<int> result = findLeaders(arr);

    cout << "Leaders in the array: ";
    for (int leader : result) {
        cout << leader << " ";
    }
    cout << endl;

    return 0;
}

Java Program to find the Leaders in an array

java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LeadersInArray {

    // Function to find leaders in the array
    public static List<Integer> findLeaders(int[] arr) {
        int n = arr.length;
        List<Integer> leaders = new ArrayList<>();

        // Initialize the rightmost element as the leader
        int currentLeader = arr[n - 1];
        leaders.add(currentLeader);

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

        // Reverse the leaders list since we traversed from right to left
        Collections.reverse(leaders);

        return leaders;
    }

    public static void main(String[] args) {
        int[] arr = {16, 17, 4, 3, 5, 2};
        List<Integer> result = findLeaders(arr);

        System.out.println("Leaders in the array: " + result);
    }
}

Python Program to find the Leaders in an array

python
# Function to find leaders in the array
def find_leaders(arr):
    n = len(arr)
    leaders = []

    # Initialize the rightmost element as the leader
    current_leader = arr[-1]
    leaders.append(current_leader)

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

    # Reverse the leaders list since we traversed from right to left
    leaders.reverse()

    return leaders

# Example usage
if __name__ == "__main__":
    arr = [16, 17, 4, 3, 5, 2]
    result = find_leaders(arr)
    print("Leaders in the array:", result)

Time Complexity:

  • O(n): We traverse the array once, where n is the length of the array.

Space Complexity:

  • O(n): The space complexity is proportional to the number of leaders found, which in the worst case can be n.

DSA

4051

323

Related Articles