GATE CS 2006 Q17 — Algorithm Design: Greedy Techniques

An element $X[i]$ is a leader if it is greater than all elements to its right, i.e., $X[i] > X[j]$ for all $j > i$.

We can find all leaders efficiently by scanning the array from right to left:

1. The rightmost element $X[n-1]$ is always a leader because there are no elements to its right. We initialize max_so_far with $X[n-1]$.
2. We traverse the array from index $n-2$ down to $0$.
3. For each element $X[i]$, if $X[i] > \text{max\_so\_far}$, then $X[i]$ is a leader. We then update $\text{max\_so\_far} = X[i]$.
4. If $X[i] \le \text{max\_so\_far}$, it is not a leader.

This approach requires only a single pass from right to left, performing a constant number of operations at each step. Thus, the time complexity is $\Theta(n)$ (linear time) and the auxiliary space complexity is $O(1)$.

Why other options are incorrect/suboptimal:

• Option A: A simple left-to-right pass cannot determine if an element is a leader without knowing the maximum of the remaining elements to its right, which would require lookaheads or auxiliary data structures.
• Option C and D: While divide-and-conquer $\Theta(n \log n)$ or a naive $\Theta(n^2)$ approach can solve the problem, they are not the best (most optimal) algorithms since $\Theta(n)$ is achievable.