Program to find leader in an array

Program to find leader in an array

Everything in the right should be smaller than current element.Two method are there.First method is brute force method but the complexity is O(n^3).But the method 2 is optimal solution that complexity is O(n).

For example

a[4]={1,5,4,3}

In the given array  1 is not leader because all the element right from 1 is greater.

5 is leader element because all the element from right from 5 is smaller than 5.

4 and 3 is also leader element.

So leader element is {5,4,3}

Method 1: brute force to find leader in a array.

#include<stdio.h>

void main() {

   int a[4]={1,5,4,3};

   int n=4;

   int i,j;

   int flag;

   int ans[3];

   for(i=0;i<n;i++)

   {

       flag=1;

       for(j=i+1;j<n;j++)

       {

           if(a[j]>a[i])

           {

               flag=0;

               break;

           }

       }

   if(flag==1)

   printf("%d",a[i]); 

   }

}

Output

5

4

3

Brute force solution is not good because complexity O(n^3)

Method 2:Optimal solution to find leader in array.

#include<stdio.h>

void main() {

   int a[4]={1,5,4,3};

   int n=4;

   int i;

   int max=0;

   for(i=n-1;i>0;i--)

   {

           if(a[i]>max)

           {

              printf("%d",a[i]);

              max=a[i];

           }

       }  

}

Output

5

4

3

But the method 2 is optimal solution that complexity is O(n).