GATE CSE 2006 | Question: 17

Question

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 

• A. solves it in linear time using a left to right pass of the array
• B. solves it in linear time using a right to left pass of the array
• C. solves it using divide and conquer in time $\Theta (n\log n)$
• D. solves it in time $\Theta( n^2)$

Comments

This Program will also work to find all such LEADER.

 

#include<stdio.h>
#include<conio.h>

void main()
{int i;
 int a[]={10,2,5,7,3,1,4,3};
 int temp=0;
 for(i=sizeof(a)/sizeof(int)-1;i>=0;i--)
 {if(a[i]>temp)
   { printf("%d ",a[i]);
     temp=a[i];
   }
 }
getch();
}

---

By right to left pass of the array we can do in O(n) time.

#include <iostream>
#include<stdio.h>
using namespace std;

int main() {
	int n;
	scanf("%d",&n);
	int a[n],max;
	for(int i=0;i<n;i++){
		scanf("%d ",&a[i]);
	}	
	max=a[n-1];
	printf("leaders are = %d ",max);
	for(int i=n-2;i>=0;i--){
		if(a[i]>max){
			max=a[i];
			printf("%d ",max);			
		}
	}
	return 0;
}

https://ideone.com/ejaIFg

 

By left to right pass of the array we can do in O(n^2) time.

#include <iostream>
#include<stdio.h>
using namespace std;

int main() {
	int n;
	scanf("%d",&n);
	int a[n],max,count;
	for(int i=0;i<n;i++){
		scanf("%d ",&a[i]);
	}	
	printf("leaders are =");
	for(int i=0;i<n;i++){
		count=1;
		for(int j=i+1;j<n;j++){
			if(a[i]<a[j]){
				count=0;
			}
		}
		if(count==1){
			printf("%d ",a[i]);
		}
	}
	return 0;
}

 

https://ideone.com/fupNEv

 

 

---

They pretty much handed out a huge hint in the options.

Answer 1

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

Comments

@Sachin Mittal 1 Sir can this question be solved using divide and conquer??

---

@abir_banerjee You can paste your solution here. What do you have in ur mind?

---

But in question says right of it so then option A is correct na

Answer 2

Ans: Option B.

http://www.geeksforgeeks.org/leaders-in-an-array/ (Method 2).

Answer 3

I think sorting the array using divide and conquer will be a better a idea so option c is correct.

Comments

No. Can be done in linear time.

---

@Arjun Sir, Sir it can be done using counting sort also.

---

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?

---

Yes it can work. And point to note here is leader is element which is greater than all element to it's right

Answer 4

\\Ref: https://www.geeksforgeeks.org/leaders-in-an-array/
1.#include <iostream> 
2.using namespace std; 
3.void printLeaders(int arr[], int size) 
4.{   int max_from_right = arr[size-1]; 
5.    /* Rightmost element is always leader */
6.	cout << max_from_right << " "; 
7.	for (int i = size-2; i >= 0; i--) 
8.{       if (max_from_right <= arr[i]) 
9.		{	max_from_right = arr[i]; 
10.			cout << max_from_right << " "; }}} 
11.int main() 
12.{   int arr[] = {16, 17, 4, 3, 5, 2}; 
13.	int n = sizeof(arr)/sizeof(arr[0]); 
14.	printLeaders(arr, n); 
15.	return 0; }	 

    Till 5th line.6thstep o/p$=2$ 

for loop 1st time. o/p$=2\ 5$

   for loop 2nd,3rd,4th time. o/p$=2\ 5\ 17$

for loop will execute 5th and 6th time also without making any changes and after that, the function will return. So $2,5,17$ are the leaders displayed in the o/p. Answer : B