An element in an array X is called a leader if it is strictly greater than all elements to...
Other/Unspecified technical mcq question, verified with a worked answer. Free to practise - no sign-up.
An element in an array $X$ is called a leader if it is strictly greater than all elements to its right. What is the time complexity of the optimal algorithm to find all leaders in an array of size $N$?
Show answer & explanation
Scanning the array from right to left while maintaining the maximum element seen so far allows determining whether each element is a leader in O(1) time per element, totaling O(N).
Step-by-step Derivation:
Step 1: Initialize max_from_right = -infinity.
Step 2: Traverse from index n-1 down to 0.
Step 3: If arr[i] > max_from_right, arr[i] is a leader and max_from_right is updated to arr[i].
Step 4: Total running time is linear O(N) with O(1) auxiliary space.