Leaders in an array refers to elements in an array that are greater than all elements to their right. In simpler terms, they are elements that dominate the array from their positions towards the end.

Problem Statement

Given an array of integers, the task is to find all the leaders in the array. A leader is an element that is greater than or equal to all elements to its right in the array. The rightmost element is always a leader since there are no elements to its right.

Examples

Example 1:

Input: arr[] = {16, 17, 4, 3, 5, 2}
Output: Leaders: [17, 5, 2]

Explanation:
The rightmost element 2 is always a leader.
Element 5 is greater than all elements to its right.
Element 17 is greater than all elements to its right.

Example 2:

Input: nums = [-3, 4, 5, 1, -4, -5]
Output: [5, 1, -4, -5]

Explanation: -5 is the rightmost element, -4 is the largest element to its right, 1 is the largest element in the index range [3, 5] and 5 is the largest element in the range [2, 5].

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The most naive thing that comes to mind is if at all any element on right is greater than the current element, then the current element can never be a leader.

Approach:

1. Iterate through each element of the array with the variable let's say i and take a boolean variable leader set at true initially which will tell if nums[i] is a leader or not.
2. For each i, iterate through the elements to the right (from i+1 to the end of the array) with the variable j & check if nums[j] is greater than nums[i], if so, reinitialize the variable leader as false and break.
3. After exiting from the inner loop, check if leader equals true, if so add nums[i] to ans vector. Finally return the answer vector.

Code:

#include<bits/stdc++.h>
using namespace std;

vector<int> printLeadersBruteForce(int arr[], int n) {
  vector<int> ans;
  
  // Iterate through each element in arr
  for (int i = 0; i < n; i++) {
    bool leader = true;

    //Checking whether arr[i] is greater than all 
    //the elements in its right side
    for (int j = i + 1; j < n; j++)
      if (arr[j] > arr[i]) {
          
        // If any element found is greater than current leader
        // curr element is not the leader.
        leader = false;
        break;
      }

    // Push all the leaders in ans array.
    if (leader)
    ans.push_back(arr[i]);

  }
  
  return ans;
}

int main() {
    
  // Array Initialization.
  int n = 6;
  int arr[n] = {10, 22, 12, 3, 0, 6};

  vector<int> ans = printLeadersBruteForce(arr,n);
  
  for(int i = 0;i<ans.size();i++){
      
      cout<<ans[i]<<" ";
  }
  
  cout<<endl;
  return 0;
}


// Output

22 12 6

Complexity Analysis:

• Time Complexity: O(N ^ 2), where N is the length of that array, as two nested for loops are used to traverse the array.
• Space Complexity: O(N).

2️⃣ Optimal Approach

Intuition:

Think of a parade where each person in a line holds a flag with a number on it, representing their importance. You start observing the parade from the last person, moving towards the front. Initially, the last person is the most important (since there's no one else behind them).

As you move forward, compare each person's flag number to the highest flag number seen so far. If someone's flag number is higher than the highest that is seen, they stand out as a leader because they have a higher number than anyone behind them.

Approach:

1. Set a variable max to the last element of the array (nums[sizeOfArray - 1]), as the last element is always a leader.
2. Create an empty list ans to store the leader elements and add the last element of the array to this list initially, as it is always a leader.
3. Start from the second last element (index = sizeOfArray - 2) and move towards the first element (index = 0)
4. For each element, compare it with the max variable. If the current element is greater than max, add this element to the ans list and update max to the current element.
5. The ans list now contains all the leader elements in the order they appear in the array.

Dry Run:

Initialization:

      +-----+-----+-----+-----+-----+-----+
arr = | 16  | 17  |  4  |  3  |  5  |  2  |
      +-----+-----+-----+-----+-----+-----+
 
 max = 2, max = arr[sizeOfArray - 1]
 
           +-----+
 leaders = |  2  |
           +-----+

First Iteration:

      +-----+-----+-----+-----+-----+-----+
arr = | 16  | 17  |  4  |  3  |  5  |  2  |
      +-----+-----+-----+-----+-----+-----+
                                 ^
                                 |
                                 i
 max = 2
           +-----+
 leaders = |  2  |
           +-----+
           
 nums[i] > max, So add nums[i] to leaders
                and update max to nums[i]
                and decrement i.

Second Iteration:

      +-----+-----+-----+-----+-----+-----+
arr = | 16  | 17  |  4  |  3  |  5  |  2  |
      +-----+-----+-----+-----+-----+-----+
                           ^
                           |
                           i
 max = 5
           +-----+-----+
 leaders = |  2  |  5  |
           +-----+-----+
           
  nums[i] < max,
  3 < 5
  decrement i by 1

Third Iteration:

      +-----+-----+-----+-----+-----+-----+
arr = | 16  | 17  |  4  |  3  |  5  |  2  |
      +-----+-----+-----+-----+-----+-----+
                     ^
                     |
                     i
 max = 5
           +-----+-----+
 leaders = |  2  |  5  |
           +-----+-----+
           
  nums[i] < max,
  4 < 5
  decrement i by 1

Fourth Iteration:

      +-----+-----+-----+-----+-----+-----+
arr = | 16  | 17  |  4  |  3  |  5  |  2  |
      +-----+-----+-----+-----+-----+-----+
               ^
               |
               i
 max = 5
           +-----+-----+
 leaders = |  2  |  5  |
           +-----+-----+
           
  nums[i] > max,
  17 > 5
  Add nums[i] to leaders,
  Update max to nums[i]
  Decrement i by 1

Fifth Iteration:

      +-----+-----+-----+-----+-----+-----+
arr = | 16  | 17  |  4  |  3  |  5  |  2  |
      +-----+-----+-----+-----+-----+-----+
         ^
         |
         i
 max = 17
           +-----+-----+-----+
 leaders = |  2  |  5  | 17  |
           +-----+-----+-----+
           
  nums[i] < max,
  16 > 17
  Decrement i by 1

Loop Termination:

      +-----+-----+-----+-----+-----+-----+
arr = | 16  | 17  |  4  |  3  |  5  |  2  |
      +-----+-----+-----+-----+-----+-----+
   ^
   |
   i
 max = 17
           +-----+-----+-----+
 leaders = |  2  |  5  | 17  |
           +-----+-----+-----+
           
  Since i went outside the bounds of the array.
  So loop will terminate.

Code:

#include<bits/stdc++.h>
using namespace std;

vector<int> printLeaders(int arr[], int n) {

  vector<int> ans;
  
 // Last element of an array is always a leader,
 // push into ans array.
 int max = arr[n - 1];
 ans.push_back(arr[n-1]);

  // Start checking from the end whether a number is greater
  // than max no. from right, hence leader.
  for (int i = n - 2; i >= 0; i--) {
    if (arr[i] > max) {
      ans.push_back(arr[i]);
      max = arr[i];
    }
  }
  
  // Reverse the vector to match the required output order
  reverse(ans.begin(), ans.end());
  
  // Return the leaders
  return ans;
}

int main() {
    
  // Array Initialization.
  int n = 6;
  int arr[n] = {10, 22, 12, 3, 0, 6};

  vector<int> ans = printLeaders(arr,n);
  
  
  for(int i = ans.size()-1;i>=0;i--){
      
      cout<<ans[i]<<" ";
  }
  
  cout<<endl;
  return 0;
}

// Output
22 12 6

Complexity Analysis:

• Time Complexity: O(N)
• Space Complexity: O(N)