Problem Statement: Given an array, print all the elements which are leaders. A Leader is an element that is greater than all of the elements on its right side in the array.
Examples:
Example 1: Input: arr = [4, 7, 1, 0] Output: 7 1 0 Explanation: Rightmost element is always a leader. 7 and 1 are greater than the elements in their right side. Example 2: Input: arr = [10, 22, 12, 3, 0, 6] Output: 22 12 6 Explanation: 6 is a leader. In addition to that, 12 is greater than all the elements in its right side (3, 0, 6), also 22 is greater than 12, 3, 0, 6.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Intuition:
There is no special intuition needed here. Just a common fact that we need to compare elements in order to find the greatest is more than enough.
Approach:
- Let’s see the basic brute force approach. The candidates for the leaders are the array elements itself.
- So, we’ll start with the first element and we’ll compare it with every other element.
- If we do not find any element greater than the starting element, then the starting element is one of the possible leaders. We print it.
- If we found at least one element greater than the current element, then it is not a leader.
- We do this for all the rest of the elements in the array and print whenever we find a leader.
Code:
C++ Code
#include<iostream>
using namespace std;
void printLeadersBruteForce(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool leader = true;
//Checking whether arr[i] is greater than all the elements in its right side
for (int j = i + 1; j < n; j++)
if (arr[j] > arr[i]) {
leader = false;
break;
}
if (leader)
cout << arr[i] << " ";
}
cout << arr[n - 1] << "\n";
}
int main() {
int arr1[] = {4, 7, 1, 0};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << "The leaders of the first array are: " << endl;
printLeadersBruteForce(arr1, n1);
int arr2[] = {10, 22, 12, 3, 0, 6};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << "The leaders of the second array are: " << endl;
printLeadersBruteForce(arr2, n2);
return 0;
}Output:
The leaders of the first array are:
7 1 0
The leaders of the second array are:
22 12 6
Time Complexity: O(n2), because for each element we are comparing with all the elements on its right side (nested for-loop).
Space Complexity: O(1), we are not using any extra space.
Java Code
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] arr1 = {4, 7, 1, 0};
System.out.println("The leaders of the first array are: ");
printLeadersBruteForce(arr1, arr1.length);
int[] arr2 = {10, 22, 12, 3, 0, 6};
System.out.println("The leaders of the second array are: ");
printLeadersBruteForce(arr2, arr2.length);
}
public static void printLeadersBruteForce(int[] arr, int n) {
for (int i = 0; i < n - 1; i++) {
boolean leader = true;
//Checking whether arr[i] is greater than all the elements in its right side
for (int j = i + 1; j < n; j++)
if (arr[j] > arr[i]) {
leader = false;
break;
}
if (leader)
System.out.print(arr[i] + " ");
}
System.out.print(arr[n - 1] + "\n");
}
}Output:
The leaders of the first array are:
7 1 0
The leaders of the second array are:
22 12 6
Time Complexity: O(n2), because for each element we are comparing with all the elements on its right side (nested for-loop).
Space Complexity: O(1), we are not using any extra space.
Solution 2:
Approach:
- In the above approach, we do a fresh traversal for each candidate. If we think carefully, we want to compare the elements on the right side only. So, what if we start from the last element.
- 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 right. Then, we move towards 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 reverse direction of their occurences. If we are concerned about the order, we can use an extra array or a string to order.
Code:
C++ Code
#include<iostream>
using namespace std;
void printLeadersOptimal(int arr[], int n) {
//Choosing the right most element as the maximum
int max = arr[n - 1];
cout << arr[n - 1] << " ";
for (int i = n - 2; i >= 0; i--)
if (arr[i] > max) {
cout << arr[i] << " ";
max = arr[i];
}
cout << "\n";
}
int main() {
int arr1[] = {4, 7, 1, 0};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << "The leaders of the first array are: " << endl;
printLeadersOptimal(arr1, n1);
int arr2[] = {10, 22, 12, 3, 0, 6};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << "The leaders of the second array are: " << endl;
printLeadersOptimal(arr2, n2);
return 0;
}Output:
The leaders of the first array are:
0 1 7
The leaders of the second array are:
6 12 22
Time Complexity: O(n), we are traversing the array only once from right to left.
Space Complexity: O(1), we are not using any extra space.
Java Code
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] arr1 = {4, 7, 1, 0};
System.out.println("The leaders of the first array are: ");
printLeadersOptimal(arr1, arr1.length);
int[] arr2 = {10, 22, 12, 3, 0, 6};
System.out.println("The leaders of the second array are: ");
printLeadersOptimal(arr2, arr2.length);
}
public static void printLeadersOptimal(int[] arr, int n) {
//Choosing the right most element as the maximum
int max = arr[n - 1];
System.out.print(arr[n - 1] + " ");
for (int i = n - 2; i >= 0; i--)
if (arr[i] > max) {
System.out.print(arr[i] + " ");
max = arr[i];
}
System.out.println();
}
}Output:
The leaders of the first array are:
0 1 7
The leaders of the second array are:
6 12 22
Time Complexity: O(n), we are traversing the array only once from right to left.
Space Complexity: O(1), we are not using any extra space.
Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article