Leaders in an Array | Brute to Optimal

This lecture covers the "Leaders in an Array" problem (also known as "Superior Elements" on various coding platforms). We will explore how to identify elements that are strictly greater than all elements to their right, transitioning from a naive $O(N^2)$ brute-force approach to an optimal $O(N)$ single-pass backward traversal.

1. Understanding the Problem & Definition of a Leader

An element in an array is called a Leader (or a Superior Element) if it is strictly greater than all the elements present on its right side.

Core Rules

An element $A[i]$ is a leader if and only if:

A[i] > A[j] \quad \forall j > i

The Last Element Rule: The last element of an array is always a leader because there are no elements to its right.

Visualizing with an Example

Consider the array: [10, 22, 12, 3, 0, 6]

CODE

Index:     0     1     2     3     4     5
Array:   [10,   22,   12,   3,    0,    6]

Is 22 a leader? Yes. The elements to its right are [12, 3, 0, 6]. Since $22$ is strictly greater than all of them, it is a leader.
Is 12 a leader? Yes. The elements to its right are [3, 0, 6]. Since $12$ is strictly greater than all of them, it is a leader.
Is 3 a leader? No. The elements to its right are [0, 6]. Since $6 > 3$ , $3$ is not a leader.
Is 10 a leader? No. Elements like 22 and 12 to its right are greater than $10$ .
Is 6 a leader? Yes. It is the last element, so there are no elements to its right to challenge it.

2. Output Format Variations

Depending on the coding platform (e.g., LeetCode, GeeksforGeeks, Coding Ninjas), the required output format for the leaders can vary:

Array Order (Original Sequence): The leaders must appear in the order they exist in the input array.
- Example Output: [22, 12, 6]
Sorted Order: The leaders must be returned in ascending sorted order.
- Example Output: [6, 12, 22]

Note: Our primary goal is to design an efficient algorithm to collect all the leaders. Once collected, we can easily format, reverse, or sort the collection to match the platform's requirements.

3. The Brute Force Approach (Naive)

The most intuitive way to solve this problem is to simulate the definition directly. For every element in the array, we perform a linear search on its right side to verify if any element is greater than or equal to it.

Algorithm Workflow

Use an outer loop with index i running from 0 to n - 1.
For each element A[i], assume it is a leader by setting a boolean flag isLeader = true.
Run an inner loop with index j from i + 1 to n - 1.
If any element A[j] >= A[i] is found, set isLeader = false and break out of the inner loop.
If isLeader remains true after checking all elements to the right, add A[i] to the answer list.

Structure & Concept Flow

Outer Loop (i)

+--> Set isLeader = true

+--> Inner Loop (j = i + 1 to n - 1)

+--> If A[j] >= A[i] ---> Set isLeader = false ---> Break

4. Brute Force Code Implementation

C++

#include <vector>

std::vector<int> getLeadersBruteForce(std::vector<int>& a) {
    std::vector<int> ans;
    int n = a.size();
    
    for (int i = 0; i < n; i++) {
        bool isLeader = true;
        
        // Check all elements to the right
        for (int j = i + 1; j < n; j++) {
            if (a[j] >= a[i]) {
                isLeader = false;
                break;
            }
        }
        
        // If no element to the right was greater or equal
        if (isLeader) {
            ans.push_back(a[i]);
        }
    }
    return ans;
}

Java

JAVA

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

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

Python

PYTHON

def get_leaders_brute_force(a: list[int]) -> list[int]:
    ans = []
    n = len(a)
    
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if a[j] >= a[i]:
                is_leader = False
                break
        if is_leader:
            ans.append(a[i])
            
    return ans

Complexity Analysis (Brute Force)

Time Complexity: $O(N^2)$ In the worst-case scenario (e.g., a sorted array in ascending order), the inner loop runs approximately $\frac{N(N-1)}{2}$ times.
Space Complexity: $O(1)$ auxiliary space. If we consider the space used to store and return the answer, the worst-case space complexity is $O(N)$ (e.g., when the array is strictly decreasing, like [5, 4, 3, 2, 1], and every element is a leader).

5. The Optimal Approach (Right-to-Left Scan)

To optimize the $O(N^2)$ time complexity, we must eliminate the redundant inner loop.

The Core Intuition

An element $A[i]$ is a leader if it is greater than the maximum element present to its right.

\text{If } A[i] > \max(A[i+1], A[i+2], \dots, A[n-1]), \text{ then } A[i] \text{ is a leader.}

By scanning the array from right to left (backwards), we can dynamically track the maximum element seen so far (maxi). This allows us to determine if the current element is a leader in $O(1)$ time.

Structure & Concept Flow

Backward Traversal Flow:

[10, 22, 12, 3, 0, 6] <--- Start scanning from index n-1 to 0

Track 'maxi' dynamically

6. Step-by-Step Walkthrough of the Optimal Approach

Let's trace the optimal algorithm on the array [10, 22, 12, 3, 0, 6]:

Initialization:
- Set maxi = INT_MIN (or a very small number).
- Initialize an empty list ans to collect leaders.
Trace Table:

Step	Index `i`	Element `A[i]`	Current `maxi`	Is `A[i] > maxi`?	Action	Updated `maxi`	Collected Leaders (`ans`)
1	5	`6`	`INT_MIN`	Yes ( $6 > -\infty$ )	Add `6` to `ans`	`6`	`[6]`
2	4	`0`	`6`	No ( $0 \ngtr 6$ )	Skip	`6`	`[6]`
3	3	`3`	`6`	No ( $3 \ngtr 6$ )	Skip	`6`	`[6]`
4	2	`12`	`6`	Yes ( $12 > 6$ )	Add `12` to `ans`	`12`	`[6, 12]`
5	1	`22`	`12`	Yes ( $22 > 12$ )	Add `22` to `ans`	`22`	`[6, 12, 22]`
6	0	`10`	`22`	No ( $10 \ngtr 22$ )	Skip	`22`	`[6, 12, 22]`

Post-Processing:
- The collected leaders in ans are [6, 12, 22].
- If original array order is required: Reverse the array ans $\rightarrow$ [22, 12, 6].
- If sorted order is required: Sort the array ans $\rightarrow$ [6, 12, 22].

7. Optimal Code Implementation

Below are the complete, production-grade implementations in C++, Java, and Python. These implementations include the sorting step to match platforms that require a sorted output.

C++

#include <vector>
#include <algorithm>
#include <climits>

std::vector<int> superiorElements(std::vector<int>& a) {
    std::vector<int> ans;
    int maxi = INT_MIN;
    int n = a.size();
    
    // Traverse the array from right to left
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] > maxi) {
            ans.push_back(a[i]);
            maxi = a[i]; // Update the maximum element on the right
        }
    }
    
    // If the platform requires sorted order:
    std::sort(ans.begin(), ans.end());
    
    // If original order was required instead, we would do:
    // std::reverse(ans.begin(), ans.end());
    
    return ans;
}

Java

JAVA

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

public class Solution {
    public static List<Integer> superiorElements(int[] a) {
        List<Integer> ans = new ArrayList<>();
        int maxi = Integer.MIN_VALUE;
        int n = a.length;
        
        // Traverse the array from right to left
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] > maxi) {
                ans.add(a[i]);
                maxi = a[i]; // Update the maximum element on the right
            }
        }
        
        // If the platform requires sorted order:
        Collections.sort(ans);
        
        // If original order was required instead, we would do:
        // Collections.reverse(ans);
        
        return ans;
    }
}

Python

PYTHON

import sys

def superior_elements(a: list[int]) -> list[int]:
    ans = []
    maxi = -sys.maxsize - 1
    n = len(a)
    
    # Traverse the array from right to left
    for i in range(n - 1, -1, -1):
        if a[i] > maxi:
            ans.append(a[i])
            maxi = a[i] # Update the maximum element on the right
            
    # If the platform requires sorted order:
    ans.sort()
    
    # If original order was required instead, we would do:
    # ans.reverse()
    
    return ans

8. Complexity Analysis (Optimal Approach)

Time Complexity

Collection Phase: $O(N)$ because we iterate through the array of size $N$ exactly once.
Formatting Phase:
- If Reversing (Original Order): $O(N)$ in the worst case.
- If Sorting (Sorted Order): $O(K \log K)$ where $K$ is the number of leaders. In the worst case (strictly decreasing array), $K = N$ , making the sorting step $O(N \log N)$ .
Total Time Complexity: $O(N)$ if only reversing is needed, or $O(N \log N)$ if sorting is required.

Space Complexity

Auxiliary Space: $O(1)$ as we only use a few variables (maxi, i, n) to perform the computation.
Output Space: $O(N)$ in the worst case to store and return the leaders.

9. Comparison of Approaches

Metric	Brute Force Approach	Optimal Approach (Reversed Output)	Optimal Approach (Sorted Output)
Time Complexity	$O(N^2)$	$O(N)$	$O(N \log N)$
Auxiliary Space	$O(1)$	$O(1)$	$O(1)$
Traversal Direction	Left-to-Right	Right-to-Left	Right-to-Left
Key Mechanism	Nested linear scan	Dynamic tracking of `maxi`	Dynamic tracking of `maxi` + sorting

Summary and Key Takeaways

Leader Definition: An element is a leader if it is strictly greater than all elements to its right.
The Last Element is Always a Leader: Because there are no elements to its right, the last element of any array always satisfies the leader condition.
Brute Force Drawback: Checking every element against all elements to its right results in redundant comparisons and an inefficient $O(N^2)$ time complexity.
Optimal Traversal Direction: Scanning the array backwards (from right to left) allows us to maintain a running maximum (maxi) of the elements processed so far.
Single-Pass Decision: With the running maximum, we can determine if any element is a leader in $O(1)$ time by checking if A[i] > maxi.
Post-Processing Flexibility: Backward traversal naturally collects leaders in reverse order. Depending on the problem constraints, we can easily reverse the output array in $O(N)$ time or sort it in $O(N \log N)$ time.

Leaders in an Array | Brute - Optimal | Strivers A2Z DSA Course

Leaders in an Array | Brute to Optimal

1. Understanding the Problem & Definition of a Leader

Core Rules

Visualizing with an Example

2. Output Format Variations

3. The Brute Force Approach (Naive)

Algorithm Workflow

4. Brute Force Code Implementation

C++

Java

Python

Complexity Analysis (Brute Force)

5. The Optimal Approach (Right-to-Left Scan)

The Core Intuition

6. Step-by-Step Walkthrough of the Optimal Approach

7. Optimal Code Implementation

C++

Java

Python

8. Complexity Analysis (Optimal Approach)

Time Complexity

Space Complexity

9. Comparison of Approaches

Summary and Key Takeaways