Table of Contents
Problem Statement
Given an array containing N elements. Find the leaders in an array. Leaders are the element that have no element larger than themselves on the right of them in the array.
Example
Input
7
1 95 4 46 8 12 21
Output
95 46 21
Explanation
Here no element present on the right side which is greater than the above numbers from there position.
In the above example, the 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.
Approach 1
Algorithm
1. Start traversing the array from the end towards the start.
2. Keep track of the 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.
Implementation
C++ Program for Find Leaders in an Array
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;//size of the array
cin>>N;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
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;
}Java Program for Find Leaders in an Array
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
System.out.println("Leaders are : ");
int cur_max = -1;
for(int i=n-1;i>=0;i--)
{
if(a[i]>cur_max)
{
System.out.print(a[i]+" ");
cur_max = a[i];
}
}
}
}7 1 95 4 46 8 12 21
Leaders are : 21 46 95
Complexity Analysis for Find Leaders in an Array
Time Complexity
O(N) where n is the size of the array. Here we traverse from the end of the array and check for leaders in the array.
Space Complexity
O(1) because we use a few variables to find our solution.
Approach 2
Algorithm
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.
Implementation
C++ Program for Find Leaders in an Array
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;//size of the array
cin>>N;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
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;
}Java Program for Find Leaders in an Array
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
System.out.println("Leaders are : ");
for(int i = 0; i < n; i++) // select an element
{
boolean 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(a[j] > a[i])//if the element on right is larger then the selected element is not a leader
{
leader = false;
break;
}
}
if(leader)
System.out.print(a[i]+" ");
}
}
}7 1 95 4 46 8 12 21
Leaders are : 95 46 21
Complexity Analysis for Find Leaders in an Array
Time Complexity
O(N*N) where N is the size of the array. Here we traverse N-i times for ith element to check for leaders in the array. This will lead us to N*N time complexity.
Space Complexity
O(1) because we use a few variables to find our solution.