Leaders in an array

Written by

Anshuman Raina

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)

 

Leaders in an array