An element in an array X is called a leader if it is greater than all elements…
2006
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.
Answer: B. Solves it in linear time using a right to left pass of the array — Best approach: scan the array from right to left and maintain the maximum seen so far to the right. Initialize currentMax to negative infinity (or a sentinel…
- 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(nlogn)
- D.
Solves it in time Theta(n^2)
Attempted by 139 students.
Show answer & explanation
Correct answer: B
Best approach: scan the array from right to left and maintain the maximum seen so far to the right.
Initialize currentMax to negative infinity (or a sentinel smaller than any array element).
For each index i from n-1 down to 0:
If A[i] > currentMax, record A[i] as a leader and set currentMax = A[i].
After the loop, the recorded leaders will be in right-to-left order; reverse them if you need left-to-right ordering.
Complexity: Time O(n), extra space O(1) (not counting output).
Example: For [16, 17, 4, 3, 5, 2], scanning right-to-left yields leaders 2 (currentMax=2), 5 (currentMax=5), 17 (currentMax=17). In left-to-right order the leaders are [17, 5, 2].
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2