Home » Technical Interview Questions » Array Interview Questions » Find Leaders in an Array

Find Leaders in an Array


Reading Time - 2 mins

Given an array containing N elements. 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.

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.

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;
}
7
1 95 4 46 8 12 21
Leaders are : 
21 46 95

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.

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

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions