LEADERS IN ARRAY

TEST TIME ON MAX EQUILIBRIUM SUM

URL: https://forms.gle/n73PA2jM3vLYM9bK7

QR CODE:
LEADERS IN ARRAY

INTRODUCTION

In an array, a leader is an element that is strictly greater than all the elements to its right.The
last element is always a leader because there are no elements to its right.

Problem Statement :

Given an array arr[] of size n, the task is to find all the Leaders in the array. An element is a
Leader if it is greater than or equal to all the elements to its right side.
Example:

Input: [2, 4, 6, 3,1 ,2] / Output: 6,3,2

Explanation

2 4 6 3 1 2

2 is the rightmost element, so it is a leader.

2 4 6 3 1 2

3 is greater than all the elements on its right side i.e. 3 is greater than 1 and 2, so it is a
leader.
 2 4 6 3 1 2

6 is greater than all the elements on its right side i.e. 6 is greater than 3, 1, and 2, so it is a
leader.

2 4 6 3 1 2

2,4 is not greater than all the elements on its right side i.e. so it is not a leader.

So, leaders are 6, 3, 2

Find all the leaders to the given array ?

Example 1:

arr = [16, 17, 4, 3, 5, 2]

Example 2:

arr = [1, 2, 3, 4, 0]

Example 3:

arr = [7, 4, 5, 7, 3]
 Approaches

1. Brute Force Approach :

To determine whether an element is greater than all the items to its right,
we begin by comparing all the elements in the array from the beginning to the
end. 1 2 3 4

2. Efficient Approach - Traversal Method :

For each candidate, conduct a new traversal. If we give it some

consideration, all of the elements on the right side are what we want to
compare. The comparison starts from right to left. 1 2 3 4
1. Brute Force Approach

There is no special intuition needed here. A common fact that we need to compare elements to find the
greatest is more than enough.

Explanation:
In this brute force approach, we start checking all the elements from the start of the array to the end to see

if an element is greater than all the elements on its right (i.e, the leader).

1 2 3 4
• For this, we will use nested loops where the outer loop will check for each element in the array

whether it is a leader or not.

• The inner loop checks if there is any element to the right that is greater than the element

currently traversed by the outer loop.

• We start by initializing the outer loop pointer to the start element and setting it as the current

leader.
• If any element traversed is found greater than the element currently set as a leader, it will not go

to the ans array and we increment the outer loop pointer by 1 and set the next element as the

current leader.

• If we don’t find any other element to the right greater than the current element, then we push the

current element to the ans array stating that is it the leader element.
Test Cases

Test Case 1 Test Case 2

Input Input
n=6 n=5
A[] = {16,17,4,3,5,2} A[] = {1,2,3,4,0}

Output Output
17 5 2 40
import java.util.*; System.out.print("Enter the number of
class Main{ elements in the array: ");
public static ArrayList<Integer> int n = sc.nextInt();
printLeadersBruteForce(int[] arr, int n){ int[] arr = new int[n];
ArrayList<Integer> ans= new ArrayList<>(); System.out.println("Enter " + n + "
for (int i = 0; i < n; i++) { elements:");
boolean leader = true; for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) arr[i] = sc.nextInt();
if (arr[j] > arr[i]) { }
leader = false; ArrayList<Integer> ans =
break; printLeadersBruteForce(arr, n);
} System.out.println("Leaders in the
if (leader) array:");
ans.add(arr[i]); for (int i = 0; i < ans.size(); i++) {
} System.out.print(ans.get(i) + " ");
return ans; }
}public static void main(String args[]) { sc.close();
Scanner sc = new Scanner(System.in); }
}
Time and space complexity

Time Complexity: O(n2)

Space Complexity: O(n)

2. Efficient Approach-traversal Method

The comparison starts from right to left

4 7 1 0 4 7 1 0

0 is Right most member, So it is one of the Leaders. 1 > 0. Only one element to it’s right.
Leaders: [0] So it is one of the Leaders.
Leaders: [0, 1]

4 7 1 0 4 7 1 0
7 is greater than all the members to it’s Right. 4 < 7 to it’s right.
So it is one of the Leaders. So it is not a Leader.
Leaders: [0, 1, 7] Leaders: [0, 1, 7]
• In the above approach, we do a fresh traversal for each candidate. we only want to compare the

elements on the right side.

• That is, we’ll try to remember the greatest element encountered so far and we’ll use that to decide
whether a candidate is a leader or not.

• First, we’ll start the traversal from the right. Then, we move toward the left. Whenever we encounter
a new element, we check with the greatest element obtained so far.
• If the current element is greater than the greatest so far, then the current element is one of the
leaders and we update the greatest element.

• Else, we proceed with the further elements on the left. This method prints the leaders in the reverse
direction of their occurrences. If we are concerned about the order, we can use an extra array or a
string to order.
import java.util.*; public static void main(String args[])
class Main{ {
public static ArrayList<Integer> int n = 6;
printLeadersBruteForce(int[] arr, int n){ int arr[]= {1, 2, 12, 13, 0, 6};
ArrayList<Integer> ans= new ArrayList<>(); ArrayList<Integer> ans=
int max = arr[n - 1]; printLeadersBruteForce(arr,n);
ans.add(arr[n-1]); Collections.sort(ans,
for (int i = n - 2; i >= 0; i--) Collections.reverseOrder());
if (arr[i] > max) { for (int i = 0; i < ans.size(); i++) {
ans.add(arr[i]); System.out.print(ans.get(i)+" ");
max = arr[i]; }
}
}
return ans; }
}
import java.util.*; static void findLeaders(int arr[], int size){
import java.lang.*; int rightMaximum=arr[arr.length-1];
public class Main System.out.print(rightMaximum+" ");
{ for (int i = size-2; i>=0; i--) {
public static void main(String[] args) { if(arr[i] > rightMaximum){
Scanner s = new Scanner(System.in); rightMaximum=arr[i];
System.out.println("Enter size of the array"); System.out.print(rightMaximum+" ");
int n = s.nextInt(); }
int[] arr = new int[n]; }
System.out.println("Enter elements of the array"); }
for (int i = 0; i < n; i++){ }
arr[i] = s.nextInt();
}
findLeaders(arr, n);}
Time and space complexity

Time Complexity: O(n)

Space Complexity: O(n)

Interview questions
1. What are leaders in an array?

Leaders in an array are the elements that are greater than all the elements to their right.
In other words, an element is a leader if it is the largest element among all the elements
to its right. Leaders can occur at the end of the array, or they can occur at any position in
the array.
Interview questions
2. What is the time complexity of your algorithm?

The time complexity of the optimized algorithm for finding leaders in an array is O(n), where n
is the length of the array. This algorithm only requires a single pass through the array, and at
each step, it performs a constant amount of work
Interview questions
3.What are some real-world applications of the algorithm for finding leaders in an
array?
1. Financial analysis: Identifying the most profitable trades in a stock market analysis.

2. Sports analytics: Identifying players with the most points, rebounds, or other statistics in a sports
game or season.

3. Web analytics: Identifying the most popular articles, videos, or other content on a website based
on views or shares.

4. Machine learning: Identifying the most important variables in a dataset by selecting those with the
highest impact on the output.

5. Computer vision: Identifying the most prominent objects in an image.

https://learn.codemithra.com
 THANK YOU

+91 78150 95095 [email protected] www.codemithra.com