Leaders in array

Leaders in array

In last post, we discussed inversions in array. One more problem on similar lines, given an array of integers, find all leaders in array. First of all, let’s understand what is a leader. Leader is an element in array which is greater than all element on right side of it. For example:
In array below element 8, 5 and 4 are leaders. Note that element at index 6 is leader by not at index 1.

leaders in array

Another example, in this there are only two leaders which is 10 and 9.

inversions in array

Clarifying question which becomes evident in example is that if last element is considered as leader? Based on answer from interviewer, function should print or not last element.

Leaders in array : thought process

What is brute force approach? Scan through all elements in array one by one and check if there is any greater element on right side. If there is no such element, number is leader in array.

package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 7.4.18.
 */
public class Leaders {

    public static ArrayList<Integer> findLeaders(int[] a){
        ArrayList<Integer> leaders = new ArrayList<>();

        for(int i=0; i<a.length; i++){
            int j = 0;
            for(j=i+1; j<a.length; j++){
                if(a[i] < a[j]){
                    break;
                }
            }
            if(j==a.length) leaders.add(a[i]);
        }

        return  leaders;

    }

    public static void main(String[] args) {
        int a[] = new int[]{90, 20, 30, 40, 50};
        ArrayList<Integer> inversions = findLeadersWithoutExtraSpace(a);
        System.out.print("Leaders : " + inversions);
    }
}

Complexity of brute force solution to find leaders in array is O(n2).

Let’s go to basics of question: All elements on right side of an element should be less than it for that element to be leader. Starting from index 0, we can assume that A[0] is leader and move forward. Remove A[0] if A[1] > A[0] as A[0] is not leader anymore. Now, if A[2] > A[1], then A[1] cannot be leader.
What if A[3] < A[2], then A[2] may still be leader and A[3] may also be.
What if A[4] > A[3], then A[3] cannot be leader. Can A[2] be leader? Depends if A[4] is less or more than A[2]. For each element, we are going back to all previous candidate leaders in reverse way and drop all candidates which are less than current element. Does it ring bell?Well, data structure which supports this kind of operation Last In First Out, is stack.
Stack supports two operations : push and pop. Question is when to push and pop and elements from stack for our problem.

Push element if it less than top of stack. If top of stack is less than current element, pop elements from stack till an element which is greater than current element. When entire array is scanned, stack will contain all leaders.

    • Start with empty stack. Push first element of array on to it.
    • For each element in array
    • Till current element is greater than top, pop element.
    • Push current element on to stack.
    •  At the end of processing, stack will contain all leaders.

Leaders in array : Implementation using stack

package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 7.4.18.
 */
public class Leaders {

    public static ArrayList<Integer> findLeadersUsingStack(int[] a){
        ArrayList<Integer> leaders =new ArrayList<>();

        Stack<Integer> s = new Stack();
        s.push(a[0]);

        for(int i=1; i<a.length; i++){
            while(s.peek() < a[i]){
                s.pop();
            }
            s.push(a[i]);
        }

        while (!s.empty()){
            leaders.add(s.pop());
        }
        return leaders;
    }
    public static void main(String[] args) {
        int a[] = new int[]{90, 20, 30, 40, 50};
        ArrayList<Integer> inversions = findLeadersWithoutExtraSpace(a);
        System.out.print("Leaders : " + inversions);
    }
}

Complexity of algorithm using stack to find leaders in array is O(n) with extra O(n) space complexity.

Scanning array in reverse
How can we avoid the additional space used by stack? When we are scanning forward, there are chances that some element going forward will be current candidate leader. That is why we keep track of all candidate leaders. How about scanning array from end, in reverse order. Start with last index and keep track of maximum we saw till current index. Check if element at current index is greater than current max, save it as leader and change current max to current element.

Algorithm to find leaders without extra space
  • Set current max as last element of array.
  • For i = n-1 to 0 index of array
    • if a[i] greater than current max
    • add a[i] to leaders.
    • Change current max to a[i]

Leaders in array implementation without extra space

package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 7.4.18.
 */
public class Leaders {

    public  static ArrayList<Integer> findLeadersWithoutExtraSpace(int[] a){
        ArrayList<Integer> leaders =new ArrayList<>();

        int currentMax = Integer.MIN_VALUE;
        for(int i=a.length-1; i>=0; i--){
            if(a[i] > currentMax ){
                currentMax = a[i];
                leaders.add(a[i]);
            }
        }

        return leaders;
    }
    public static void main(String[] args) {
        int a[] = new int[]{90, 20, 30, 40, 50};
        ArrayList<Integer> inversions = findLeadersWithoutExtraSpace(a);
        System.out.print("Leaders : " + inversions);
    }
}

Complexity of reverse array algorithm to find leaders in array is O(n) with no added space complexity.

Please share you views,suggestion, queries or if you find something wrong. If you want t contribute to algorithms and me, please reach out to us on communications@algorithmsandme.com