Leaders in array
In one of our precious post, we discussed inversions in array, today, let’s discuss another problem on array. Problem statement is : 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:
A = [5,4,1,3,2] Leaders in array : 5, 4 and 3 A = [10,6,3,1,7,9] leaders : 10
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 does not print last element.
Methods to find leaders in array
Scan through all elements in array one by one and then check if there is any element on right side of it and greater than it. If there is no such element, number is leader in array.
Complexity of brute force solution to find leaders in array is O(n2).
Let’s see if we can use stack here. There two operations which are supported on stack : push and pop. Question is when to push and pop and elements from stack. Push element if it less than top of stack. If top of stack is less than current element, pop elements from stack till we find an element which is greater than current. When entire array is scanned, stack will contain all leaders. Algorithm is given below:
1. Start with empty stack. Push first element on to it. 2. For each element in array 2.a Till current element is greater than top, pop element. 2.b Push current element on to stack. 3. At the end of processing, stack will contain all leaders.
Complexity of algorithm using stack to find leaders in array is O(n) with extra O(n) space complexity.
Scanning array in reverse
To avoid extra space used in stack method, scan given array in reverse order. Start with last element till 0th index, check if current element is greater than current max, print the element as that would be leader. Also, change the current max. Algorithm is given below:
1. Set current max as last element of array. 2. For i = n-1 to 0 index of array 2.a if a[i] greater than current Max Print a[i] Change current max to a[i] 3. At the end all printed elements will be leaders.
Leaders in array implementation
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. Also, please share if you like the article. Sharing is caring.