Leaders In An Array – Data Structures & Algorithms – Brain Mentors Skip to content

Leaders In An Array – Data Structures & Algorithms

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.

  • By using Scan Array from Right approach the Time complexity of Leaders in an array is Big O(n).  
  • Because 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 
  • 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

Big O(n) is less than Big O(n2). That means Scan Array from right approach is an optimized or best approach to find the leaders in an array which is done in lesser time than the brute force approach.

Now see the practical examples one by one for both the approaches.

The first practical example is for Approach – 1 that is Brute Force Algorithm:

CODE :
OUTPUT:

First, create one project. In the main() function, create one array and call the function. Then create a function definition that is used to find leaders in the array. In function take two parameters one is an array and the second is the size of this array parameter. 

Next, create two loops, the 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. In the inner loop create one if block to check that if the picked element is less than or equal to its right side elements. So we can jump out the inner loop if the condition is true by using a break keyword. That means it is not a leader. 

And outside the inner loop, we can check that if ‘j’ is equal to the size of the array which means it is a leader of the array because the picked element is compared with all its right side elements. 



The second practical example is for Approach – 2 that is Scan Array from Right:

CODE :
OUTPUT:

First, create one project. In the main() function, create one array and call the function. Then create a function definition that is used to find leaders in the array. In function take two parameters one is an array and the second is the size of this array parameter. 

Keep one maxElement Variable in it that is used as the highest variable. Next create one loop, So that we can traverse from right to left side of the array which means n-1 to 0. And inside the loop, create one if block to check that 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 the first approach that is the brute force approach is called Naive Solution for this problem. And Scan Array from right is called as Best Solution for this problem.

That’s all for now. Hope you have learned something through my Blog. I will see you in the next Data Structures and Algorithms blog. If you are interested in Data Structures and Algorithms, then you also opt for our exclusive Brain Mentor’s Data Structures and Algorithms Online Course.

Sign Up and Start Learning