CODEWITHSUNDEEP
algorithm
suresh
suresh

Reputation: 4224

leader of the array

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

Upvotes: 1

Views: 4081

Answers (5)

Arpan Das
Arpan Das

Reputation: 1037

Algorithm to solve the problem :

Start from the right keeping track of largest element (currentLeader). If a larger element is found, then print it and set currentLeader to the current element. We can consider the last element is a leader since there is no element to its right.

https://www.tuturself.com/posts/view?menuId=82&postId=943

Upvotes: 0

David M
David M

Reputation: 72860

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.

Upvotes: 12

suresh
suresh

Reputation: 4224

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];
 }
}

Upvotes: 0

Daren Thomas
Daren Thomas

Reputation: 70314

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

Upvotes: 0

Ingo
Ingo

Reputation: 36339

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.

Upvotes: 0

Related Questions