Return to Revisions

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

1. Solves it in linear time using a left to right pass of the array

2. Solves it in linear time using a right to left pass of the array

3. Solves it using divide and conquer in time Θ(nlogn)

4. Solves it in time Θ(n^2)

My attempt :

#include <iostream>
using namespace std;
/* C++ Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
 int max_from_right = arr[size-1];
 /* Rightmost element is always leader */
 cout << max_from_right << " ";
 for (int i = size-2; i >= 0; i--)
 {
 if (max_from_right < arr[i])
 { 
 max_from_right = arr[i];
 cout << max_from_right << " ";
 }
 } 
}
/* Driver program to test above function*/
int main()
{
 int arr[] = {16, 17, 4, 3, 5, 2};
 int n = sizeof(arr)/sizeof(arr[0]);
 printLeaders(arr, n);
 return 0;
} 

At the start the right most element will always be a leader. If an element is greater than our current_max, it will a leader. Add this element to leaders. Set current_max to this element and carry on leftward. Time Complexity would be O(n).

Can you give algorithm in another way or better way to find leader in array ?