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>
{
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;
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]);
printf("\n\n");
return 0;
}``````

## All 4 Replies

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 flag = false;
int intHighest = a[n-1];

for(int i=(n-2); i >= 0; i--)
{
if(a[i] > intHighest)
{
flag = true;
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};

{
}

{
}
}``````
commented: That's it.......A very good solution +1
``````#include <stdio.h>

{
bool flag = false;
int intHighest = a[n-1];

for(int i=(n-2); i >= 0; i--)
{
if(a[i] > intHighest)
{
flag = true;
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};

{
}

{
}
}``````

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 flag = false;
int intHighest = a[n-1];
int i=0;

for(i=(n-2); i >= 0; i--)
{
if(a[i] > intHighest)
{
flag = true;
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};

{