Leaders in an array
Written by
Leaders in an array Problem
PROBLEM: Print all the LEADERS in the array. An element is a leader if it is greater than the elements to its right in the array.
Input: [32, 2, 4, 2, 5, 17, 24, 22]
Output: [32, 34, 22]
# Brute Force
Pseudo Code:
- We start a loop and iterate till the second last element.
- Inside another loop, we iterate over elements to its right( to the last index) to check if it is a leader
- If it is greater than all elements, we mark it as a leader.
- The rightmost is added after the loop ends.
Code:
#include <iostream> using namespace std;
void printLeader(int arr[], int size) { for (int iterator = 0; iterator< size; iterator++) { int innerIterator;
for (innerIterator = iterator + 1; innerIterator < size; innerIterator++) { if (arr[iterator] <= arr[innerIterator]) break; } if (innerIterator == size) cout << arr[iterator] << " "; }
}
int main() { int arr[] = { 32, 2, 4, 2, 5, 17, 24, 22 }; cout << "Leaders are { "; printLeader(arr, 8); cout << "}"; return 0; }
Output:
Leaders are { 32, 24, 22 }
Time Complexity: O(N*N)
Space Complexity: O(1)
# Optimized Approach
Pseudo Code:
- We start a loop from the right.
- We keep checking the max value. As soon as a max is found, print it.
- End.
Code:
#include <iostream> using namespace std;
void printLeadersOptimized(int arr[], int size)
{ int maxRight = arr[size - 1]; cout << maxRight << " "; for (int iterator = size - 2; iterator >= 0; iterator--) { if (maxRight < arr[iterator]) { maxRight = arr[iterator]; cout << maxRight << " "; } } }
int main() { int arr[] = { 32, 2, 4, 2, 5, 17, 24, 22 }; cout << "Leaders are { "; printLeadersOptimized(arr, 8); cout << "}"; return 0; }
Output:
Leaders are { 32, 24, 22 }
Time Complexity: O(N)
Space Complexity: O(1)