Leaders in an array

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:

1. We start a loop and iterate till the second last element.
2. Inside another loop, we iterate over elements to its right( to the last index) to check if it is a leader
3. If it is greater than all elements, we mark it as a leader.
4. 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 &lt; size; innerIterator++)
	{
		if (arr[iterator] &lt;= arr[innerIterator])
			break;
	}

	if (innerIterator == size)
		cout &lt;&lt; arr[iterator] &lt;&lt; " ";
}

}
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:

1. We start a loop from the right.
2. We keep checking the max value. As soon as a max is found, print it.
3. 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)