edited by
17,696 views
58 votes
58 votes

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 by

7 Answers

Best answer
64 votes
64 votes

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 by
3 votes
3 votes
I think sorting the array using divide and conquer will be a better a idea so option c is correct.
edited by
1 votes
1 votes
\\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:

Related questions