Given an array of elements. An element is called as a leader if it is greater than all
the elements to the right of it. Print all the leaders in O(n)?

The following is my approach.Can anyone tell me how to improve the code and also the current time complexity?
Is recursion more efficient in this case?

#include<stdio.h>
void findLeaders(int a[],int n)
{
 int i,j=n-1,flag=0;
 for(i=0;i<n;i++)
 {
   if(a[i] > a[i+1])
   {
	while(a[i]>a[j])
	{
		if((i+1) ==j) 
		{
			flag=1;
			printf("\nleader = %d",a[i]);
		        break;
		}
		else   j--;
	}
	j=n-1;
   }
 }
 if(!flag)  printf("\nNo leader in the given array\n");
}
 

int main()
{
 int a[100],n=0,i=0;
 printf("\nEnter n:");
 scanf("%d",&n);
 for(i=0;i<n;i++)
	scanf("%d",&a[i]);
 findLeaders(a,n);
 printf("\n\n");
 return 0;
}

Thanks in advance.

Edited 7 Years Ago by want_to_code: more information

Yes, start at the RIGHT-most (highest) element and work your way backwards.

When you run across a value that's higher, it's a leader.

#include <stdio.h>

bool findLeaders(int a[],int n)
{
	bool flag = false;
	int intHighest = a[n-1];

	for(int i=(n-2); i >= 0; i--)
		{
		if(a[i] > intHighest)
			{
			flag = true;
			printf("\nleader = %d", a[i]);
			intHighest = a[i];
			}
		}
	return flag; // returns fals if no leaders
}
void main(void)
{
	static int a[] = {5,1,2,7,3,4,6};
	static int b[] = {9,1,2,8,3,4,6,7};

	if(!findLeaders(a, (sizeof(a)/sizeof(int))))
		{
		puts("No Leaders in a");
		}

	if(!findLeaders(b, (sizeof(b)/sizeof(int))))
		{
		puts("No Leaders in b");
		}
}
Comments
That's it.......A very good solution
#include <stdio.h>

bool findLeaders(int a[],int n)
{
	bool flag = false;
	int intHighest = a[n-1];

	for(int i=(n-2); i >= 0; i--)
		{
		if(a[i] > intHighest)
			{
			flag = true;
			printf("\nleader = %d", a[i]);
			intHighest = a[i];
			}
		}
	return flag; // returns fals if no leaders
}
void main(void)
{
	static int a[] = {5,1,2,7,3,4,6};
	static int b[] = {9,1,2,8,3,4,6,7};

	if(!findLeaders(a, (sizeof(a)/sizeof(int))))
		{
		puts("No Leaders in a");
		}

	if(!findLeaders(b, (sizeof(b)/sizeof(int))))
		{
		puts("No Leaders in b");
		}
}

i heard that bool is supported by gcc compiler ( for a c program)
but when i saved this file in .c extension and executed, it gave me errors as bool is unrecognized identifer.

is there any special header we need to include for that.

you can use "int" or you can use a typedef
typedef enum {false, true} bool;

This version will compile under gcc:

// ParseLeaders.cpp : Defines the entry point for the console application.
//

#include <stdio.h>

typedef enum {false, true} bool;

bool findLeaders(int a[],int n)
{
	bool flag = false;
	int intHighest = a[n-1];
	int i=0;

	for(i=(n-2); i >= 0; i--)
		{
		if(a[i] > intHighest)
			{
			flag = true;
			printf("\nleader = %d", a[i]);
			intHighest = a[i];
			}
		}
	return flag; // returns fals if no leaders
}
int main(void)
{
	static int a[] = {5,1,2,7,3,4,6};
	static int b[] = {9,1,2,8,3,4,6,7};

	if(!findLeaders(a, (sizeof(a)/sizeof(int))))
		{
		puts("No Leaders in a");
		}

	if(!findLeaders(b, (sizeof(b)/sizeof(int))))
		{
		puts("No Leaders in b");
		}

	return 0;
}

Edited 7 Years Ago by thines01: clarity

This article has been dead for over six months. Start a new discussion instead.