Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example in the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.
Let the input array be arr[] and length of the array be size.
Method 1 (Simple)
Use two loops. The outer loop runs from 0 to size – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then the picked element is the leader.
Python
# Python Function to print leaders in array def printLeaders(arr,size): for i in range(0, size): for j in range(i+1, size): if arr[i]<=arr[j]: break if j == size-1: # If loop didn't break print arr[i], # Driver function arr=[16, 17, 4, 3, 5, 2] printLeaders(arr, len(arr)) # This code is contributed by _Devesh Agrawal__ |
Output:
17 5 2
Time Complexity: O(n*n)
Auxiliary Space: O(1)
As constant extra space is used.
Method 2 (Scan from right)
Scan all the elements from right to left in an array and keep track of maximum till now. When maximum changes its value, print it.
Below image is a dry run of the above approach:
Below is the implementation of the above approach:
Python
# Python function to print leaders in array def printLeaders(arr, size): max_from_right = arr[size-1] print max_from_right, for i in range( size-2, -1, -1): if max_from_right < arr[i]: print arr[i], max_from_right = arr[i] # Driver function arr = [16, 17, 4, 3, 5, 2] printLeaders(arr, len(arr)) # This code contributed by _Devesh Agrawal__ |
Output:
2 5 17
Time Complexity: O(n)
Auxiliary Space: O(1)
Method 3
In this approach, we start from the second-last element of the array and compare it with the last element. If the second-last element is greater than the last element, then it is a leader, and we store it in a list. We then update the current leader to be the second-last element.
We repeat this process for all the elements of the array, and in the end, we reverse the list of leaders and print it.
Python
def printLeaders(arr, size): leader = arr[size-1] leaders = [leader] for i in range(size-2, -1, -1): if arr[i] > leader: leader = arr[i] leaders.append(leader) leaders.reverse() print(leaders) # Driver function arr = [16, 17, 4, 3, 5, 2] printLeaders(arr, len(arr)) |
[17, 5, 2]
Time Complexity: O(n), where n is the size of the array
Auxiliary Space: O(n)
The extra space is used to store the elements of max_from_right array.
Please refer complete article on Leaders in an array for more details!
