Leaders in an array

Problem: You are given an array. You have to write a program that will print all the leaders in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader.

For example array {6, 7, 4, 3, 5, 2}, leaders are 7, 5 and 2.

This is very common data structure interview question.

Method 1 (Brute Force)
Use two loops. The outer loop runs from 0 to length – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then the picked element is the leader.

Time Complexity: O(n*n)

Method 2 (Scan the array from right)
Start Traversing from the right side of the array, and keep the highest element in a variable,if we find any element greater then this variable print it and update the variable with the new value.

void printLeaders(int arr[], int n)
	int maximum =  arr[n-1];
	int i;

	// Rightmost element is always leader
	printf("%d ", maximum);
	for(i = n-2; i >= 0; i--)
		if(maximum < arr[i])
		   printf("%d ", arr[i]);
		   maximum = arr[i];

int main()
  int arr[] = {6, 7, 4, 3, 5, 2};
  printLeaders(arr, 6);
  return 0;  

Output: 2 5 7

Time Complexity: O(n)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation