Find Leaders in an Array Optimal Right to Left Scan Solution

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Input Array Leaders Description
[16, 17, 4, 3, 5, 2] [17, 5, 2] 17 > [4,3,5,2], 5 > 2, and 2 is last so it's a leader
[1, 2, 3, 4, 5] [5] Only 5 is greater than all elements to its right (none)
[5, 4, 3, 2, 1] [5, 4, 3, 2, 1] Each element is greater than all elements to its right
[7] [7] Single element is always a leader
[] [] Empty array, so no leaders
[10, 10, 10] [10] Only the last occurrence is considered a leader
[0, -1, -2, -3] [0, -1, -2, -3] All elements are leaders in descending order

Solution❯

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).

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)The array is scanned from right to left once, and each element is checked only once, making the operation linear.
Average CaseO(n)Regardless of input distribution, the array is always scanned once from end to start to compare with the running maximum.
Worst CaseO(n)In the worst case (e.g., strictly decreasing array), every element becomes a leader, but the time taken remains linear as there is still only one pass.

Space Complexity❯

O(n)

Explanation: 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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...