Home » Interview » Array Interview Questions » Find leaders in an array

# Find leaders in an array

## Find the leaders in an array. Leaders are the element who have no element larger than themselves on the right of them in the array

Given an array, we will find the leaders of the array and print them. Leaders are the elements, who have no element larger than themselves on the right of them in the array.

### Example

Input

1 95 4 46 8 12 21

Output

In the above example, last element(ie, 21) is always the leader as it has no element on the right of it. 46, 95 are also leaders as no element is greater than them on the right of the array

## ALGORITHM 1

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(1)

1.    Start traversing the array from the end towards the start.
2.    Keep track of current maximum obtained.
3.    For each element if the element is greater than the current maximum then that is a leader because on its right there was no number larger than it.Then simply print the element and make it the new current maximum.
4.    Else keep traversing till start.

## C++ Program

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

int main()
{
int arr[] = {27, 39, 15, 12, 18, 4}; //Array
int N = sizeof(arr)/sizeof(arr[0]); //size of array
int cur_max = INT_MIN;

for(int i = N-1; i>=0 ; i--)
{
if(arr[i] > cur_max)
{
cout << arr[i] <<" ";
cur_max = arr[i];
}
}

return 0;
}

## ALGORITHM 2

Time Complexity – O(n*n)

1. Start  traversing the array from the start to the end.
2. Pick all the elements one by one, For each picked element, compare the elements to its right.
a. If the picked element is greater than all the elements to its right     side, then the picked element is the leader.
b. else, It is not the leader

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

int main()
{
int arr[] = {27, 39, 15, 12, 18, 4}; //Array
int N = sizeof(arr)/sizeof(arr[0]); //size of array
for(int i = 0; i < N; i++) // select an element
{
bool leader = true; // assume it to be greater than all the elements on the right side
for(int j = i+1; j<N; j++)// loop through all the elements in the right of the selected element
{
if(arr[j] > arr[i])//if the element on right is larger then the selected element is not a leader
{
break;
}
}
cout<<arr[i]<<" ";
}

return 0;
}

Normal
0

false
false
false

EN-US
X-NONE
X-NONE