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)$
edited | 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.

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)$.

edited
+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};
for(i=6;i>=0;i--)
{
{
}
}
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 ...

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 a[]={14,2,1,13,12,11,20,24};
for(i=n;i>=0;i--)
{
for(i=n-1;i>=0;i--)
{
{

}
}
}
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 a[8]={50,40,1,13,12,11,20,24};

for(i=7;i>=0;i--)
{
{

}
}

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

Ans: Option B.

edited by
I think sorting the array using divide and conquer will be a better a idea so option c is correct.
edited by
+2
No. Can be done in linear time.
0
@Arjun Sir, Sir it can be done using counting sort also.
0

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