R@M3$H.NBlog

[ARRAY] Leader in an Array

25 September, 2013 - 4 min read

An array element X is one of leaders of the array if the all the elements following that array element is lesser than or equal to the array element X.

Work from the right hand end of the array, keeping track of the maximum value you have encountered. Every time that maximum increases or is equalled, that element is a leader by your definition. What is more, it stays a leader regardless of what happens further to the left - in other words, every leader you add to your list is a genuine leader, not just a candidate, as you'd have working left to right.

 

Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.

Let the input array be arr[] and size of the array be size.

Method 1 (Simple)
Use two loops. The outer loop runs from 0 to size – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then the picked element is the leader.

/*Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
  int i, j;
  for (i = 0; i < size; i++)
  {
    for (j = i+1; j < size; j++)
    {
        if(arr[i] <= arr[j])
          break;
    }   
    if(j == size) // the loop didn't break
    {
        printf("%d ", arr[i]);
    }
  }
}
/*Driver program to test above function*/
int main()
{
  int arr[] = {16, 17, 4, 3, 5, 2};
  printLeaders(arr, 6);
  getchar();
}
// Output:  17 5 2

Time Complexity: O(n*n)

Method 2 (Scan from right)
Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print it.

/*Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
  int max_from_right =  arr[size-1];
  int i;
  /* Rightmost element is always leader */
  printf("%d ", max_from_right);
    
  for(i = size-2; i >= 0; i--)
  {
    if(max_from_right < arr[i])
    {
       printf("%d ", arr[i]);
       max_from_right = arr[i];
    }
  }   
}
/*Driver program to test above function*/
int main()
{
  int arr[] = {16, 17, 4, 3, 5, 2};
  printLeaders(arr, 6);
  getchar();   
}   
// Output:  2 5 17

__
Time Complexity:__ O(n)

 

void FindLeader ( int Arr[], int ArrSize ) {
int max = Arr[ArrSize-1] ;
for ( int i = ArrSize-1; i >= 0; i-- ) {
if ( Arr[i] >= max ) {
cout << Arr[i] << " " ;
max = Arr[i] ;
}
}
cout << endl ;
}

 

Method-3:

We can use stack for left to right pass..

For each element .. before pushing it pop all the elements that are less than it , so in the end stack has only leaders left in it

{
This can be also done will the help of stack.
push the first element in the stack // s-> 16
push another element,
if ( upcoming element is smaller then the element of the top of the stack )
Push(element);
else
pop() till you find element bigger then the upcoming element.
}
left over elements in the stack will be leaders !!! :)
ex:
s-> 16 //pop 16 push 17
s-> 17 //push 4
s->17 ,4. // push 3
s->17 ,4,3, // pop till you element bigger than 5 then push
s-> 17,5// push 2
s->17,5,2
all elements left in the stack are leaders :)

 

END