RUN
C C++ JAVA PYTHON SQL HTML CSS DSA Robotics AWS SDE PREPARATION

Made with  & Code

# Leaders in an array Problem

Written By -

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;

{
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 { ";
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;

{
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 { ";
cout << "}";
return 0;
}``````

Output:

`Leaders are { 32, 24, 22 }`

Time Complexity: O(N)

Space Complexity: O(1)