leader of the array

Question

Consider an array element X is one of leaders of the array if the all the elements following that array element is lesser than or equal to the array element X ...then what is the best algorithm to find all the leaders of the array?

Array may have more leaders.. consider the following array [10 9 8 6 ] then 10,9,8 are leaders of the array

Answer 1

Work from the right hand end of the array, keeping track of the maximum value you have encountered. Every time that maximum increases or is equalled, that element is a leader by your definition. What is more, it stays a leader regardless of what happens further to the left - in other words, every leader you add to your list is a genuine leader, not just a candidate, as you'd have working left to right.

Answer 2

Maintain a list of possible leaders as you work through the array/list. This list is naturally sorted descending. Each new element is a possible new leader. If its bigger than the last found possible leader, then you have to eliminate all leaders smaller than this new possible leader and append it to the now truncated list. Otherwise, just append it to the list of possible leaders.

Python:

def findleaders(array):
    leaders = []
    for element in array:
        if element < leaders[-1]:
            # new possible leader
            leaders.append(element)
        else:
            # remove false possible leaders
            while leaders[-1] < element:
                leaders.pop()
                if not leaders: break #stop when list is empty
            leaders.append(element)
    return leaders

Answer 3

In Haskell it would look like

 leaders [] = [];

leaders (a:as)
          | all (a>) as = a : leaders as
          | otherwise   = leaders as

giving the list of leaders of a list.

• The list of leaders of an empty list is empty
• If the first element of a list is a leader, then this is also the first element of the list of leaders.

It should be easy to adapt to arrays.

Answer 4

Deriving from David M's algorithm

int max = a[LAST_INDEX]
for( int i = a[LAST_INDEX-1] ; i >=0 ; i-- ) {
 if( a[i] > max ) 
 {      
   printf("%d",a[i]);
   max = a[i];
 }
}