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

Slight modification of Next greater element
 

int curr_max = arr[n-1];
cout << arr[n-1] << " is a leader" << endl; // last element is always a leader

for(int i = n - 2; i >= 0; i--){
    if(arr[i] > curr_max){
        cout << arr[i] << " is a leader" << endl;
        curr_max = arr[i];
    }
}

 

---

thank you very much

---

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side

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

what will happen if we go from left to right can anybody pls explain?

---

The number of Comparision Will increase if we go from Left to Right, and it is asked "The Best Algo"

---

we need to ignore the ambiguity that first element will be leader or not i think.. ( though it does'nt affect the answer )

Answer 2

Ans: Option B.

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

Answer 3

Here is an example :

Answer 4

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 5

\\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

Answer 6

I think, that this problem is only reverse sorting or putting elements in descending order,

In order to do that start scanning from right.

So. ANSWER is B.