Leaders in an array is an easy problem of arrays from Data Structures and Algorithms. Leaders in the array mean that element is greater than all its right side elements of the array.
So there are two approaches to find the leaders in an array:
Brute Force Algorithm
Scan Array from Right
1. Brute Force Algorithm
As you can see, we have an array of size 5. In this approach, we can traverse the array from left to right and each element picks one by one and check with all its right side elements of the array, which is used to checking that it is greater or not than its right side elements of the array. So those are greater than their right side elements of the array, then they become the leaders of this given array.
The rightmost element is always a leader because there is no element to the right side.
So the leaders of this given array are 20, 6, and 5. So let me explain it.
The first element is 14 which is not greater than with all its right side elements because 14 is not greater than 20. The second element is 20 which is greater than with all its right side elements. So it is the first leader. The third element is 3 which is not greater than with all its right side elements because 3 is not greater than 6 and 5. The fourth element is 6 which is greater than with all its right side elements. So it is a second leader. Fifth and last element is 5 which is the rightmost element and it is always a leader as there is no element to its right side. And that’s why leaders are: 20, 6, and 5.
By using the brute force approach the Time complexity of Leaders in an array is Big O(n2).
Because In this approach we use two loops
Outer loop is used to traverse the array from 0 to n-1
And pick one by one all the elements of the array from left to right
Then the inner loop is used to compares the picked element with all the elements to its right side
2. Scan Array from Right
As you can see, we have an array of size 5. In this approach, we traverse from right to left side of the array. Keep the one highest variable in it that is used as the highest variable and if we find any element that is greater than this highest variable then we print this element as a leader and update the highest variable with the new value.
So here maxElement is treated as the highest variable with initial value is equal to 0. And if we find any element that is greater than this maxElement then we print this element as a leader and update the maxElement with the new value.
So the leaders of this given array are 5, 6, and 20. So let me explain it.
The first element is 5 which is greater than this maxElement as maxElement is equal to 0. So the first leader is 5 and the updated value of maxElement is 5. The second element is 6 which is greater than maxElement as maxElement is equal to 5. So the second leader is 6. And the updated value of maxElement is 6. The third element is 3 which is not greater than maxElement as maxElement is equal to 6. So it is not a leader. The fourth element is 20 which is greater than maxElement as maxElement is equal to 6. So the third leader is 20. And the updated value of maxElement is 20. The fifth element is 14 which is not greater than maxElement as maxElement is equal to 20. So it is not a leader. And that’s why leaders are: 5, 6, and 20.
Read Full Article Here – https://brain-mentors.com/leaders-in-an-array/