Leaders in an Array

Given an array of integers, your task is to find all the leader elements in the array.

• A leader is an element that is greater than all the elements to its right in the array.
• The rightmost element is always a leader because there are no elements after it.

You need to return a list of all such leaders in left-to-right order as they appear in the array.

Understanding the Problem

We are given an array of integers, and we are asked to find all the leaders in the array.

A leader is defined as an element that is strictly greater than all the elements to its right.

This means we need to check, for each element, whether there is any greater element after it. If not, it's a leader.

Why start from the end?

The last element in the array has no elements after it. So, it is always a leader.

We will scan the array from right to left, keeping track of the current maximum. Every time we find a number greater than this maximum, we consider it a new leader.

Step-by-Step Approach (With Example)

Let’s take the example [16, 17, 4, 3, 5, 2] and go through the solution step by step.

1. Start from the last element: 2. It has no elements to its right, so it’s a leader.
2. Next element to the left: 5. Since 5 > 2, it’s a leader. Update the current maximum to 5.
3. Next: 3. Since 3 < 5, it is NOT a leader.
4. Next: 4. Since 4 < 5, it is NOT a leader.
5. Next: 17. Since 17 > 5, it is a leader. Update the current maximum to 17.
6. Finally: 16. Since 16 < 17, it is NOT a leader.

We collected the leaders in reverse order: [2, 5, 17]. So we reverse the list to get the final answer: [17, 5, 2].

Handling Edge Cases

• Increasing Array: [1, 2, 3, 4, 5] – Only the last element 5 is a leader.
• Decreasing Array: [5, 4, 3, 2, 1] – All elements are leaders since each is greater than those after it.
• Equal Elements: [10, 10, 10] – Only the last one is a leader. Leaders must be strictly greater.
• Single Element: [7] – The only element is always a leader.
• Empty Array: [] – No elements, so no leaders. Return an empty list.

Final Explanation

To solve the problem efficiently, we scan the array once from right to left, maintaining a max_so_far variable. Every time we find an element greater than max_so_far, we add it to our list of leaders.

Since we find leaders from the right side, we reverse the list at the end to maintain the original left-to-right order.

This gives us an efficient solution with O(n) time complexity and O(n) space complexity (for storing leaders).

1. Given an array arr.
2. Initialize an empty list leaders to store leader elements.
3. Start from the last element: initialize max_from_right = arr[n-1].
4. Add max_from_right to the leaders list.
5. Traverse the array from right to left:
6. → If current element is greater than max_from_right, update max_from_right and add it to leaders.
7. After the loop, reverse the leaders list to maintain left-to-right order.

#include <stdio.h>

void findLeaders(int arr[], int n) {
    int maxFromRight = arr[n - 1];
    int leaders[n], k = 0;
    leaders[k++] = maxFromRight;
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] > maxFromRight) {
            maxFromRight = arr[i];
            leaders[k++] = maxFromRight;
        }
    }
    printf("Leaders: ");
    for (int i = k - 1; i >= 0; i--) {
        printf("%d ", leaders[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    findLeaders(arr, n);
    return 0;
}

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

vector<int> findLeaders(vector<int>& arr) {
    int n = arr.size();
    vector<int> leaders;
    int maxFromRight = arr[n - 1];
    leaders.push_back(maxFromRight);
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] > maxFromRight) {
            maxFromRight = arr[i];
            leaders.push_back(maxFromRight);
        }
    }
    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: ";
    for (int num : result) cout << num << " ";
    return 0;
}

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

arr = [16, 17, 4, 3, 5, 2]
print("Leaders:", find_leaders(arr))

import java.util.*;

public class LeadersInArray {
    public static List<Integer> findLeaders(int[] arr) {
        int n = arr.length;
        List<Integer> leaders = new ArrayList<>();
        int maxFromRight = arr[n - 1];
        leaders.add(maxFromRight);
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > maxFromRight) {
                maxFromRight = arr[i];
                leaders.add(maxFromRight);
            }
        }
        Collections.reverse(leaders);
        return leaders;
    }

    public static void main(String[] args) {
        int[] arr = {16, 17, 4, 3, 5, 2};
        System.out.println("Leaders: " + findLeaders(arr));
    }
}

function findLeaders(arr) {
    let n = arr.length;
    let leaders = [];
    let maxFromRight = arr[n - 1];
    leaders.push(maxFromRight);
    for (let i = n - 2; i >= 0; i--) {
        if (arr[i] > maxFromRight) {
            maxFromRight = arr[i];
            leaders.push(maxFromRight);
        }
    }
    leaders.reverse();
    return leaders;
}

const arr = [16, 17, 4, 3, 5, 2];
console.log("Leaders:", findLeaders(arr));

package main

import (
    "fmt"
)

func findLeaders(arr []int) []int {
    n := len(arr)
    leaders := []int{}
    maxFromRight := arr[n-1]
    leaders = append(leaders, maxFromRight)
    for i := n - 2; i >= 0; i-- {
        if arr[i] > maxFromRight {
            maxFromRight = arr[i]
            leaders = append(leaders, maxFromRight)
        }
    }
    // Reverse the leaders slice
    for i, j := 0, len(leaders)-1; i < j; i, j = i+1, j-1 {
        leaders[i], leaders[j] = leaders[j], leaders[i]
    }
    return leaders
}

func main() {
    arr := []int{16, 17, 4, 3, 5, 2}
    result := findLeaders(arr)
    fmt.Print("Leaders: ")
    for _, val := range result {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

fn find_leaders(arr: &Vec<i32>) -> Vec<i32> {
    let n = arr.len();
    let mut leaders = vec![];
    let mut max_from_right = arr[n - 1];
    leaders.push(max_from_right);
    for i in (0..n - 1).rev() {
        if arr[i] > max_from_right {
            max_from_right = arr[i];
            leaders.push(max_from_right);
        }
    }
    leaders.reverse();
    leaders
}

fn main() {
    let arr = vec![16, 17, 4, 3, 5, 2];
    let leaders = find_leaders(&arr);
    print!("Leaders: ");
    for val in leaders {
        print!("{} ", val);
    }
    println!();
}

fun findLeaders(arr: IntArray): List<Int> {
    val leaders = mutableListOf<Int>()
    var maxFromRight = arr.last()
    leaders.add(maxFromRight)
    for (i in arr.size - 2 downTo 0) {
        if (arr[i] > maxFromRight) {
            maxFromRight = arr[i]
            leaders.add(maxFromRight)
        }
    }
    leaders.reverse()
    return leaders
}

fun main() {
    val arr = intArrayOf(16, 17, 4, 3, 5, 2)
    println("Leaders: ${findLeaders(arr)}")
}

func findLeaders(_ arr: [Int]) -> [Int] {
    var leaders = [Int]()
    var maxFromRight = arr.last!
    leaders.append(maxFromRight)
    for i in stride(from: arr.count - 2, through: 0, by: -1) {
        if arr[i] > maxFromRight {
            maxFromRight = arr[i]
            leaders.append(maxFromRight)
        }
    }
    return leaders.reversed()
}

let arr = [16, 17, 4, 3, 5, 2]
print("Leaders:", findLeaders(arr))

function findLeaders(arr: number[]): number[] {
    let leaders: number[] = [];
    let maxFromRight = arr[arr.length - 1];
    leaders.push(maxFromRight);
    for (let i = arr.length - 2; i >= 0; i--) {
        if (arr[i] > maxFromRight) {
            maxFromRight = arr[i];
            leaders.push(maxFromRight);
        }
    }
    leaders.reverse();
    return leaders;
}

const arr: number[] = [16, 17, 4, 3, 5, 2];
console.log("Leaders:", findLeaders(arr));

Time complexity

Space complexity

O(n)

The worst-case space is O(n) if all elements are leaders and stored in the list. Additional space is used only for the leaders list and a few variables.