The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
2.6k views

An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array 

  1. solves it in linear time using a left to right pass of the array
  2. solves it in linear time using a right to left pass of the array
  3. solves it using divide and conquer in time $\Theta (n\log n)$
  4. solves it in time $\Theta( n^2)$
asked in Algorithms by Active (3.7k points)
edited by | 2.6k views
+10

Suppose given array is [42, 32, 1, 5, 8, 10, 7, 4]
Start to scan from right, right most element is always a leader, print it.
4
we have to move to left and print that number which is greater than the immediate last leader.
4 is the immediate last leader, 7 > 4, so 7 is also a leader.
10 > 7 = print 7, and now 10 is a leader.
8 < 10, skip 8
5 < 10, skip 5
1 < 10, skip 1,
32 > 10, print 32
42 > 32, print 42

T.C is $O(n)$, only one scan is required.

0
Simple Note :-

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.
0
@Manu Bhai can we do this by applying counting sort? It will take O(n) extra space.

4 Answers

+35 votes
Best answer

Option B) We can move from right to left, while keeping a note of the maximum element so far (let's call it current_max).

  •  Starting from the rightmost element, we initialize our current_max with it, since the rightmost element will always be a leader.
  •  Moving from right to left, if an element $x$ is greater than our current_max, then $x$ is also a leader. Add this element to list of leaders (or simply print it). Set current_max to $x$ and carry-on leftward.

Time Complexity would be $\Theta(n)$.

answered by Active (2.4k points)
edited by
+4
This Program will work to find all such LEADER.

#include <stdio.h>
int main()
{
       int a[]={14,2,1,13,12,11,20,24};
        int lead=a[7],i;
        for(i=6;i>=0;i--)
        {        
        if(a[i]<lead)
            {
                lead=a[i];
                printf("%d ",lead);
             }
        }   
     return 0;
}
0
why not option A... here also u can also traverse the whole array in linear time....
+1
no because leader will always be in right side
+3
@Abhishek it should be ...

if(lead<a[i])
0

@Abhishek and @VS

code should be like this,rt? because we need to " find all leaders in an array  "

    #include <stdio.h>
    int main()
    {
    	   int lead,i,n;
           int a[]={14,2,1,13,12,11,20,24};
           for(i=n;i>=0;i--)
           {
            	lead=a[n];
            	for(i=n-1;i>=0;i--)
            	{        
            	if(a[i]>lead)
                	{
                    lead=a[i];
 
                	}
                 }
            printf("%d ",lead);
            }   
         return 0;
    }

but still some error is there in code. R u getting the error?

+4

@srestha mam

   #include <stdio.h>
   #include <iostream>
   
   using namespace std;
   
    int main()
    {
           int lead,i,n=8;
           int a[8]={50,40,1,13,12,11,20,24};
           
                lead=a[7];
                cout<<lead<<" ";
                for(i=7;i>=0;i--)
                {        
                if(a[i]>lead)
                    {
                    lead=a[i];
                    cout<<lead<<" ";
 
                    }
                 }
            
              
         return 0;
    }

OUTPUT :: 24 40 50

An element in an array X is called a leader if it is greater than all elements to the  right of it in X.

  int a[8]={50,40,1,13,12,11,20,24};

Starting from back 24 is a leader.

Now , 20 < 24 hence not a leader

Now what we are doing is keeping a record of the maximum element found in our right subarray and

We are checking if our current element under check is greater than this maximum element,If so that means that element is greater than all the elements to its right and hence a leader.

For example ::

When we reach 40.. Lead=24(max till now) ,since 40>24 the maximum it implies it is greater than all elements to its right and hence 40 is a Leader. Similarly for 50.

+4

https://gateoverflow.in/user/srestha  it can be done using option A... bt will take  $$O(n^{n})$$  time ... So b is ans cause it will take O(n) time

0
@Puja

Can u give some algorithm , which are u telling
+7
+1
Very good @puja

That is what called a good learner
+6 votes
answered by Active (4.8k points)
edited by
+2 votes
I think sorting the array using divide and conquer will be a better a idea so option c is correct.
answered by Boss (14.3k points)
edited by
+2
No. Can be done in linear time.
0
@Arjun Sir, Sir it can be done using counting sort also.
0
Sir, its asking to find ALL the leaders.

Means for every element we have to ensure that all elements to the right are less than elemnt.

In limear time we can only find a single leader.

Wouldn't sorting be a better option?
0
Yes it can work. And point to note here is leader is element which is greater than all element to it's right
–1 vote

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.

#include<iostream>

using namespace std;

/*C++ Function to print leaders in an array */

void printLeaders(int arr[], int size)

{

    for (int i = 0; i < size; i++)

    {

        int j;

        for (j = i+1; j < size; j++)

        {

            if (arr[i] <= arr[j])

                break;

        }   

        if (j == size) // the loop didn't break

            cout << arr[i] << " ";

  }

}

/* Driver program to test above function */

int main()

{

    int arr[] = {16, 17, 4, 3, 5, 2};

    int n = sizeof(arr)/sizeof(arr[0]);

    printLeaders(arr, n);

    return 0;

}

answered by Loyal (9k points)
0
Ur coding will take O($n^{n}$) in worst case .... Bt the answer should be O($n$) ....
0
@puja for option a y it can't be n*n for n elements we are traversing n times approximately so n*n how will u conclude it will be n^n plzzzzzz tell me if I'm wrong let me know how to think
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,748 questions
47,471 answers
145,584 comments
62,234 users