Leaders in an Array

Problem Statement

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

An element is called a leader if it is greater than or equal to all the elements to its right side.

The rightmost element is always a leader.

Example 1

Input

arr = [16, 17, 4, 3, 5, 2]

Output

17 5 2

Explanation

• 17 is greater than all elements to its right
• 5 is greater than 2
• 2 is the last element

Example 2

Input

arr = [7, 10, 4, 10, 6, 5, 2]

Output

10 10 6 5 2

Why This Problem Is Important

• Common interview question
• Tests:
  • Array traversal
  • Comparison logic
  • Right-to-left scanning
• Forms the base for:
  • Suffix maximum problems
  • Stock buy-sell variants
  • Monotonic patterns

Approaches Overview

Approach 1: Brute Force Method

Idea

For each element, check all elements to its right.
If no element on the right is greater, then the current element is a leader.

Algorithm

1. Traverse array from index 0 to n-1
2. Assume arr[i] is a leader
3. Compare it with all elements to the right
4. If any element is greater, it is not a leader
5. Print all valid leaders

Time and Space Complexity

• Time Complexity: O(n²)
• Space Complexity: O(1)

C Implementation 

#include<stdio.h> 

int main() {
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = 6;

    for(int i = 0; i < n; i++) {
        int isLeader = 1;

        for(int j = i + 1; j < n; j++) {
            if(arr[j] > arr[i]) {
                isLeader = 0;
                break;
            }
        }

        if(isLeader)
            printf("%d ", arr[i]);
    }
    return 0;
}

Output

17 5 2

C++ Implementation 

#include<iostream> 
using namespace std;

int main() {
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = 6;

    for(int i = 0; i < n; i++) {
        bool isLeader = true;

        for(int j = i + 1; j < n; j++) {
            if(arr[j] > arr[i]) {
                isLeader = false;
                break;
            }
        }

        if(isLeader)
            cout << arr[i] << " ";
    }
    return 0;
}

Java Implementation 

public class LeadersBruteForce {
    public static void main(String[] args) {
        int[] arr = {16, 17, 4, 3, 5, 2};

        for(int i = 0; i < arr.length; i++) {
            boolean isLeader = true;

            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] > arr[i]) {
                    isLeader = false;
                    break;
                }
            }

            if(isLeader)
                System.out.print(arr[i] + " ");
        }
    }
}

Python Implementation 

arr = [16, 17, 4, 3, 5, 2]
n = len(arr)

for i in range(n):
    is_leader = True
    for j in range(i + 1, n):
        if arr[j] > arr[i]:
            is_leader = False
            break
    if is_leader:
        print(arr[i], end=" ")

JavaScript Implementation 

let arr = [16, 17, 4, 3, 5, 2];
let n = arr.length;

for (let i = 0; i < n; i++) {
    let isLeader = true;

    for (let j = i + 1; j < n; j++) {
        if (arr[j] > arr[i]) {
            isLeader = false;
            break;
        }
    }

    if (isLeader)
        process.stdout.write(arr[i] + " ");
}

.

Approach 2: Optimized Method (Right-to-Left Traversal)

Idea

• Traverse the array from right to left
• Keep track of the maximum element seen so far
• If the current element is greater than or equal to this maximum, it is a leader

Algorithm

1. Initialize maxRight = arr[n-1]
2. Add maxRight to result
3. Traverse from index n-2 to 0
4. If arr[i] >= maxRight:
   • Update maxRight
   • Add element to result
5. Reverse result for correct order

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1) (excluding output list)

C Implementation 

#include<stdio.h> 

int main() {
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = 6;

    int maxRight = arr[n - 1];
    int leaders[6], k = 0;

    leaders[k++] = maxRight;

    for(int i = n - 2; i >= 0; i--) {
        if(arr[i] >= maxRight) {
            maxRight = arr[i];
            leaders[k++] = arr[i];
        }
    }

    for(int i = k - 1; i >= 0; i--)
        printf("%d ", leaders[i]);

    return 0;
}

C++ Implementation 

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

int main() {
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = 6;

    vector leaders;
    int maxRight = arr[n - 1];
    leaders.push_back(maxRight);

    for(int i = n - 2; i >= 0; i--) {
        if(arr[i] >= maxRight) {
            maxRight = arr[i];
            leaders.push_back(arr[i]);
        }
    }

    for(int i = leaders.size() - 1; i >= 0; i--)
        cout << leaders[i] << " ";

    return 0;
}

Java Implementation 

import java.util.*;

public class LeadersOptimized {
    public static void main(String[] args) {
        int[] arr = {16, 17, 4, 3, 5, 2};

        List leaders = new ArrayList<>();
        int maxRight = arr[arr.length - 1];
        leaders.add(maxRight);

        for(int i = arr.length - 2; i >= 0; i--) {
            if(arr[i] >= maxRight) {
                maxRight = arr[i];
                leaders.add(arr[i]);
            }
        }

        Collections.reverse(leaders);
        for(int num : leaders)
            System.out.print(num + " ");
    }
}

Python Implementation 

arr = [16, 17, 4, 3, 5, 2]

leaders = []
max_right = arr[-1]
leaders.append(max_right)

for i in range(len(arr) - 2, -1, -1):
    if arr[i] >= max_right:
        max_right = arr[i]
        leaders.append(arr[i])

leaders.reverse()
print(*leaders)

JavaScript Implementation 

let arr = [16, 17, 4, 3, 5, 2];
let n = arr.length;

let leaders = [];
let maxRight = arr[n - 1];
leaders.push(maxRight);

for (let i = n - 2; i >= 0; i--) {
    if (arr[i] >= maxRight) {
        maxRight = arr[i];
        leaders.push(arr[i]);
    }
}

leaders.reverse();
console.log(leaders.join(" "));

Dry Run (Optimized Approach)

Array: [16, 17, 4, 3, 5, 2]

Start from right:
max = 2 → leader
5 > 2 → leader
17 > 5 → leader

Final leaders: 17 5 2

Summary

• Leaders are elements greater than all elements to their right
• Brute force is simple but inefficient
• Optimized approach is preferred in interviews
• Right-to-left traversal reduces time complexity to O(n)

Next Problems in the Series

Equilibrium Index of an Array