NIELIT 2016 MAR Scientist C - Section C: 53

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

Answer 1

(B) is the correct answer.

for the detailed explanation. 

https://www.geeksforgeeks.org/leaders-in-an-array/

Comments

to find leaders just do a scan from right to left in the array. This will be done in linear time O(n).

So, the correct option (B).

Answer 2

Do a scan from right to left, and keep storing the max. element encountered till that point.

Whenever an element greater than max. is encountered, it is a leader.

Answer 3

B,C,D  ALL ARE POSSIBLE WHEN WE TRY TO FIND A LEADER BUT

QUESN ASKS BEST ALGORITHIM SO SIMPLY OPTION B IS BEST