Leaders in an array

Given an array of integers, print the leaders in the array. A leader is an element which is larger than all the elements in the array to its right.
For example:
Input Array:
{ 98, 23, 54, 12, 20, 7, 27 }
Output:
Leaders- 27 54 98

Algorithm

Start from the right keeping track of largest element (currentLeader). If a larger element is found, then print it and set currentLeader to the current element.
Note that the last element is a leader since there is no element to its right.
The solution can be visualized by considering array elements as towers and printing towers which are visible if seen through right view of the array.
Please note that leaders will be seen in sorted order when seen from right(right view of the towers).

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)

 

Code

#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;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*