Write a program to print all the LEADERS in an array in C++

This article will guide you on how to write an efficient program to print all the LEADERS in an array in C++ programming. An element is called the leader of an array if there is no element greater than it on the right side. For example, if the array elements are

1)arr[]={7,10,4,3,6,5,2}
Leaders are 10,6,5,2 since there are no elements greater than them on the right side.
2)arr[]={10,20,30}
Leader is 30.

Approach:

We should observe that the rightmost element is always a leader. If there is an array that is sorted in increasing order, then the last element will be the leader because every other element will have a greater element on the right side.

We will first solve the question using a simple method. In this approach, we use two loops. The outer loop runs from 0 to n-1 (n is the size of the array). The inner loop helps us to compare the element which is picked to all the elements on the right side. If the element which is picked is greater than all the other elements to the right side of it, then this element will be the leader.  We break out of the loop if the element is smaller in value than the element on the right. Time complexity is O(n*n).

Implementation using C++:

The C++ code is written below:

#include<iostream> 
using namespace std; 
  
/*C++ Function to print the leaders in an array */
void leaders(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
    { 
        int j; 
        for (j = i+1; j<n; j++) 
        { 
            if (arr[i] <= arr[j]) 
                break; 
        }     
        if (j == n) 
            cout << arr[i] << " "; 
  } 
} 

int main() 
{ 
    int arr[] = {7,10,4,3,6,5,2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    leaders(arr, n); 
    return 0; 
}

 

Output: 
10 6 5 2

Efficient method:

Now we will use an efficient method to solve the problem. In this method, we will traverse from the right side of the array, and keep the maximum element in a variable(max). If we find any element greater than max, we print that element and update max with the new value.

Below is the required C++ code:

#include<iostream> 
using namespace std; 
  
/*C++ Function to print the leaders in an array */
void leaders(int arr[], int n)
{
    int max = arr[n-1];
    int i;
 
    // Rightmost element is always leader
    printf("%d ", max);
      
    for(i = n-2; i >= 0; i--)
    {
        if(max < arr[i])
        {
           printf("%d ", arr[i]);
           max = arr[i];
        }
    }   
}
 
int main()
{
  int arr[] = {7,10,4,3,6,5,2};
  leaders(arr, 7);
  return 0; 
}
Output:
2 5 6 10

This will print the leaders in reverse order since we are traversing from the right side of the array.

Time complexity is O(n).

Thank you for reading. I hope this helps.

Leave a Reply