Geeks For Geeks - Problem of the Day | POTD | 18 Aug

Leaders in an array

Given an array A of positive integers. Your task is to find the leaders in the array. An element of array is leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.
Example 1:

Input: n = 6 A[] = {16,17,4,3,5,2}
Output: 17 5 2 Explanation: The first leader is 17 as it is greater than all the elements to its right. Similarly, the next
leader is 5. The right most element is always a leader so it is also
included.

Example 2:

Input: n = 5 A[] = {1,2,3,4,0}
Output: 4 0

Explanation: 0 is the rightmost element and 4 is the only element which is greater than all the elements to its right.

Your Task:

You don't need to read input or print anything. The task is to complete the function leader() which takes array A and n as input parameters and returns an array of leaders in order of their appearance.

Expected Time Complexity: O(n)

Expected Auxiliary Space: O(n)

Constraints:

1 <= n <= 107

0 <= Ai <= 107
Link to the Question

Solution

Approach:

The idea is last element is always going to be the Leader(as there is no element on it's right) and if we can find an element greator than it on left than it's also leader.In this way we get the leader's in reverse;

Algorithm:

• intialize a vector/array with the last elemtent of the array
• maintain a variable of last Leader
• traverse the array in reverse and if an element greator than the last leader is encountered update last leader and push it to the resulting vector/array
• Doing so we get the leader array in reverse so simply reverse the array and return it.

Time Complexity: time to traverse + time to reverse = O(N) + O(N/2) = O(N);

Space Complexity: O(N) as all element can be leader in worst case of array being sorted in reverse order.

c++ code:

 vector<int> leaders(int a[], int n){
        // Code here
        vector<int> res = {a[n-1]};

        int crL = a[n-1];

        for(int i = n-2;i>=0;i--){
            if(crL<=a[i]){
                crL = a[i];
                res.push_back(crL);
            }

        }

       reverse(res.begin(),res.end());
        return res;

    }