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

leaders are 95 46 21

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
    cout<<"Leaders are : \n";	
		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;
}
Try It

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
    cout<<"Leaders are : \n";
		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
						{
							leader = false;
							break;
						}
				}
			if(leader)
			cout<<arr[i]<<" ";
		}
	
	return 0;
}
Try It


Next > < Prev
Scroll to Top