Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Array Leaders

MEDIUMProblemSolveExternal Links

Description

You are given an array of positive integers. Your task is to find all the leader elements in the array.

An element is considered a leader if it is greater than or equal to every element that appears to its right in the array. In other words, there is no element after it that is strictly greater than it.

The rightmost element of the array is always a leader, since there are no elements to its right.

Return all the leaders in the order they appear in the original array.

Examples

Example 1

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 only element to its right [2] is smaller than 5.
  • 2 is a leader because it is the rightmost element — there are no elements to its right.
  • 16 is NOT a leader because 17 (to its right) is greater than 16.
  • 4 is NOT a leader because 5 (to its right) is greater than 4.
  • 3 is NOT a leader because 5 (to its right) is greater than 3.

Example 2

Input: arr = [10, 4, 2, 4, 1]

Output: [10, 4, 4, 1]

Explanation:

  • 10 is a leader because all elements to its right [4, 2, 4, 1] are ≤ 10.
  • The first 4 (index 1) is a leader because all elements to its right [2, 4, 1] have no value strictly greater than 4. Note that the second 4 is equal, not greater, so the first 4 still qualifies.
  • 2 is NOT a leader because 4 (to its right) is greater than 2.
  • The second 4 (index 3) is a leader because the only element to its right [1] is smaller than 4.
  • 1 is a leader because it is the rightmost element.

Example 3

Input: arr = [5, 10, 20, 40]

Output: [40]

Explanation: When the array is sorted in strictly increasing order, only the rightmost element (the largest) is a leader. Every other element has a larger element to its right.

Constraints

  • 1 ≤ arr.length ≤ 10^6
  • 0 ≤ arr[i] ≤ 10^6

Editorial

Brute Force

Intuition

The most straightforward way to check if an element is a leader is to follow the definition literally: for each element, look at every element to its right and verify that none of them is strictly greater.

Imagine you are standing in a line of people of different heights. You want to know if you are taller than or as tall as everyone standing behind you. The simplest way to check is to turn around and compare your height with each person behind you, one by one. If nobody behind you is taller, you are a leader. You repeat this check for every person in the line.

Step-by-Step Explanation

Let's trace through arr = [16, 17, 4, 3, 5, 2]:

Step 1: Check arr[0] = 16. Compare with all elements to its right: [17, 4, 3, 5, 2].

  • 17 > 16 → STOP. 16 is NOT a leader.

Step 2: Check arr[1] = 17. Compare with all elements to its right: [4, 3, 5, 2].

  • 4 < 17 ✓, 3 < 17 ✓, 5 < 17 ✓, 2 < 17 ✓ → All are smaller. 17 IS a leader.

Step 3: Check arr[2] = 4. Compare with elements to its right: [3, 5, 2].

  • 3 < 4 ✓, but 5 > 4 → STOP. 4 is NOT a leader.

Step 4: Check arr[3] = 3. Compare with elements to its right: [5, 2].

  • 5 > 3 → STOP. 3 is NOT a leader.

Step 5: Check arr[4] = 5. Compare with elements to its right: [2].

  • 2 < 5 ✓ → All are smaller. 5 IS a leader.

Step 6: Check arr[5] = 2. It is the last element, so it is automatically a leader.

Result: Leaders = [17, 5, 2]

Brute Force — Check Each Element Against All Right Neighbors — For each element, we scan every element to its right. If we find one that is strictly greater, the element is not a leader. Otherwise, it is.

Algorithm

  1. Initialize an empty result list.
  2. For each element arr[i] from index 0 to n-1:
    a. Set a flag isLeader = true.
    b. For each element arr[j] from index i+1 to n-1:
    • If arr[j] > arr[i], set isLeader = false and break.
      c. If isLeader is still true, add arr[i] to the result.
  3. Return the result list.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> leaders(vector<int>& arr) {
        vector<int> result;
        int n = arr.size();
        
        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) {
                result.push_back(arr[i]);
            }
        }
        
        return result;
    }
};
class Solution:
    def leaders(self, arr):
        result = []
        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:
                result.append(arr[i])
        
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> leaders(int[] arr) {
        List<Integer> result = new ArrayList<>();
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            boolean isLeader = true;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i]) {
                    isLeader = false;
                    break;
                }
            }
            if (isLeader) {
                result.add(arr[i]);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times. For each element, the inner loop can run up to n-1 times in the worst case (when the array is sorted in non-increasing order, every element is a leader and the inner loop runs fully). Total comparisons in the worst case: n × (n-1) / 2, which is O(n²).

Space Complexity: O(1)

We only use a boolean flag and loop counters. The result list is part of the output and not counted as extra space. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity. With n up to 10^6, this means up to 5 × 10^11 operations in the worst case — far too slow for any reasonable time limit (typically 10^7 to 10^8 operations per second).

The core problem is redundant work: when checking if arr[i] is a leader, we scan everything to its right. But then when checking arr[i+1], we scan almost the same subarray again. We are recalculating the maximum of the right portion from scratch for every element.

Key insight: Instead of repeatedly asking "is this element ≥ everything to its right?", we can flip the perspective. If we traverse from right to left and keep track of the maximum value seen so far, then at each position we simply compare the current element with this running maximum. If it is greater than or equal to the maximum, it is a leader. This turns each element's check from O(n) to O(1), giving us O(n) total.

Optimal Approach - Suffix Maximum (Right-to-Left Scan)

Intuition

Instead of checking each element against all the elements to its right, we reverse the traversal direction. We walk from the rightmost element to the leftmost, maintaining a single variable: the maximum value we have seen so far from the right.

Think of it this way: imagine you are walking backward through the line of people. You remember the tallest person you have passed so far. At each new person, you only need to ask one question: "Are you at least as tall as the tallest person I've seen behind you?" If yes, you are a leader, and you also become the new tallest person seen. If no, you are not a leader. This single comparison per person is the key to O(n) efficiency.

The rightmost element starts as the initial maximum and is always a leader. As we move left, whenever we find an element that is ≥ the current maximum, it means nothing to its right is strictly larger — so it qualifies as a leader.

Step-by-Step Explanation

Let's trace through arr = [16, 17, 4, 3, 5, 2]:

Step 1: Start from the rightmost element. Set maxRight = arr[5] = 2. Add 2 to result. Result (building in reverse): [2].

Step 2: Move to i=4, arr[4] = 5. Is 5 ≥ maxRight (2)? YES. 5 is a leader. Update maxRight = 5. Add 5 to result. Result: [2, 5].

Step 3: Move to i=3, arr[3] = 3. Is 3 ≥ maxRight (5)? NO. 3 is NOT a leader. maxRight stays 5.

Step 4: Move to i=2, arr[2] = 4. Is 4 ≥ maxRight (5)? NO. 4 is NOT a leader. maxRight stays 5.

Step 5: Move to i=1, arr[1] = 17. Is 17 ≥ maxRight (5)? YES. 17 is a leader. Update maxRight = 17. Add 17 to result. Result: [2, 5, 17].

Step 6: Move to i=0, arr[0] = 16. Is 16 ≥ maxRight (17)? NO. 16 is NOT a leader. maxRight stays 17.

Step 7: Reverse the result to maintain original order: [17, 5, 2].

Result: [17, 5, 2]

Suffix Maximum — Right-to-Left Leader Detection — Watch how a single right-to-left scan with a running maximum identifies all leaders in O(n) time. We compare each element against the suffix maximum — if it's greater or equal, it's a leader.

Algorithm

  1. Initialize an empty result list.
  2. Set maxRight = arr[n - 1] (the last element).
  3. Add maxRight to the result list (rightmost element is always a leader).
  4. Traverse the array from index n-2 down to 0:
    a. If arr[i] ≥ maxRight:
    • Update maxRight = arr[i]
    • Add arr[i] to the result list
  5. Reverse the result list to restore the original left-to-right order.
  6. Return the result.

Code

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

class Solution {
public:
    vector<int> leaders(vector<int>& arr) {
        vector<int> result;
        int n = arr.size();
        
        // Start with the rightmost element
        int maxRight = arr[n - 1];
        result.push_back(maxRight);
        
        // Traverse from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] >= maxRight) {
                maxRight = arr[i];
                result.push_back(maxRight);
            }
        }
        
        // Reverse to maintain original order
        reverse(result.begin(), result.end());
        
        return result;
    }
};
class Solution:
    def leaders(self, arr):
        result = []
        n = len(arr)
        
        # Start with the rightmost element
        max_right = arr[n - 1]
        result.append(max_right)
        
        # Traverse from right to left
        for i in range(n - 2, -1, -1):
            if arr[i] >= max_right:
                max_right = arr[i]
                result.append(max_right)
        
        # Reverse to maintain original order
        result.reverse()
        
        return result
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> leaders(int[] arr) {
        List<Integer> result = new ArrayList<>();
        int n = arr.length;
        
        // Start with the rightmost element
        int maxRight = arr[n - 1];
        result.add(maxRight);
        
        // Traverse from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] >= maxRight) {
                maxRight = arr[i];
                result.add(maxRight);
            }
        }
        
        // Reverse to maintain original order
        Collections.reverse(result);
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once from right to left, performing a constant-time comparison and possible update at each position. The final reverse operation is also O(n) in the worst case (if all elements are leaders). Total: O(n) + O(n) = O(n).

Space Complexity: O(1)

We use only a single variable (maxRight) as extra space. The result list is part of the output and is not counted as auxiliary space. The reverse is done in-place on the result list.