Write a program to 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 int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.
Let the input array be arr[] and size of the array be size.
Method 1 (Simple)
Use two loops. The outer loop runs from 0 to size – 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.
C++
#include<iostream>
usingnamespacestd;
/*C++ Function to print leaders in an array */
voidprintLeaders(intarr[], intsize)
{
for(inti = 0; i < size; i++)
{
intj;
for(j = i+1; j < size; j++)
{
if(arr[i] <= arr[j])
break;
}
if(j == size) // the loop didn't break
cout << arr[i] << " ";
}
}
/* Driver program to test above function */
intmain()
{
intarr[] = {16, 17, 4, 3, 5, 2};
intn = sizeof(arr)/sizeof(arr[0]);
printLeaders(arr, n);
return0;
}
Java
classLeadersInArray
{
/*Java Function to print leaders in an array */
voidprintLeaders(intarr[], intsize)
{
for(inti = 0; i < size; i++)
{
intj;
for(j = i + 1; j < size; j++)
{
if(arr[i] <= arr[j])
break;
}
if(j == size) // the loop didn't break
System.out.print(arr[i] + " ");
}
}
/* Driver program to test above functions */
publicstaticvoidmain(String[] args)
{
LeadersInArray lead = newLeadersInArray();
intarr[] = newint[]{16, 17, 4, 3, 5, 2};
intn = arr.length;
lead.printLeaders(arr, n);
}
}
Python
# Python Function to print leaders in array
defprintLeaders(arr,size):
fori inrange(0, size):
forj inrange(i+1, size):
ifarr[i]<=arr[j]:
break
ifj ==size-1: # If loop didn't break
printarr[i],
# Driver function
arr=[16, 17, 4, 3, 5, 2]
printLeaders(arr, len(arr))
# This code is contributed by _Devesh Agrawal__
C#
// C# program to print
// leaders in array
usingSystem;
classGFG
{
voidprintLeaders(int[]arr,
intsize)
{
for(inti = 0; i < size; i++)
{
intj;
for(j = i + 1; j < size; j++)
{
if(arr[i] <= arr[j])
break;
}
// the loop didn't break
if(j == size)
Console.Write(arr[i] + " ");
}
}
// Driver Code
publicstaticvoidMain()
{
GFG lead = newGFG();
int[]arr = newint[]{16, 17, 4, 3, 5, 2};
intn = arr.Length;
lead.printLeaders(arr, n);
}
}
// This code is contributed by
// Akanksha Rai(Abby_akku)
PHP
<?php
// PHP Function to print
// leaders in an array
functionprintLeaders($arr, $size)
{
for($i= 0; $i< $size; $i++)
{
for($j= $i+ 1;
$j< $size; $j++)
{
if($arr[$i] <= $arr[$j])
break;
}
// the loop didn't break
if($j== $size)
echo($arr[$i] . " ");
}
}
// Driver Code
$arr= array(16, 17, 4, 3, 5, 2);
$n= sizeof($arr);
printLeaders($arr, $n);
// This code is contributed
// by Shivi_Aggarwal
?>
Output:
17 5 2
Time Complexity: O(n*n)
Method 2 (Scan from right)
Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print it.
C++
#include <iostream>
usingnamespacestd;
/* C++ Function to print leaders in an array */
voidprintLeaders(intarr[], intsize)
{
intmax_from_right = arr[size-1];
/* Rightmost element is always leader */
cout << max_from_right << " ";
for(inti = size-2; i >= 0; i--)
{
if(max_from_right < arr[i])
{
max_from_right = arr[i];
cout << max_from_right << " ";
}
}
}
/* Driver program to test above function*/
intmain()
{
intarr[] = {16, 17, 4, 3, 5, 2};
intn = sizeof(arr)/sizeof(arr[0]);
printLeaders(arr, n);
return0;
}
Java
classLeadersInArray
{
/* Java Function to print leaders in an array */
voidprintLeaders(intarr[], intsize)
{
intmax_from_right = arr[size-1];
/* Rightmost element is always leader */
System.out.print(max_from_right + " ");
for(inti = size-2; i >= 0; i--)
{
if(max_from_right < arr[i])
{
max_from_right = arr[i];
System.out.print(max_from_right + " ");
}
}
}
/* Driver program to test above functions */
publicstaticvoidmain(String[] args)
{
LeadersInArray lead = newLeadersInArray();
intarr[] = newint[]{16, 17, 4, 3, 5, 2};
intn = arr.length;
lead.printLeaders(arr, n);
}
}
Python
# Python function to print leaders in array
defprintLeaders(arr, size):
max_from_right =arr[size-1]
printmax_from_right,
fori inrange( size-2, 0, -1):
ifmax_from_right < arr[i]:
printarr[i],
max_from_right =arr[i]
# Driver function
arr =[16, 17, 4, 3, 5, 2]
printLeaders(arr, len(arr))
# This code contributed by _Devesh Agrawal__
C#
// C# program to find Leaders in an array
usingSystem;
classLeadersInArray {
// C# Function to print leaders
// in an array
voidprintLeaders(int[]arr, intsize)
{
intmax_from_right = arr[size - 1];
// Rightmost element is always leader
Console.Write(max_from_right +" ");
for(inti = size - 2; i >= 0; i--)
{
if(max_from_right < arr[i])
{
max_from_right = arr[i];
Console.Write(max_from_right +" ");
}
}
}
// Driver Code
publicstaticvoidMain(String[] args)
{
LeadersInArray lead = newLeadersInArray();
int[]arr = newint[]{16, 17, 4, 3, 5, 2};
intn = arr.Length;
lead.printLeaders(arr, n);
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP Function to print
// leaders in an array
functionprintLeaders(&$arr, $size)
{
$max_from_right= $arr[$size- 1];
// Rightmost element
// is always leader
echo($max_from_right);
echo(" ");
for($i= $size- 2;
$i>= 0; $i--)
{
if($max_from_right< $arr[$i])
{
$max_from_right= $arr[$i];
echo($max_from_right);
echo(" ");
}
}
}
// Driver Code
$arr= array(16, 17, 4, 3, 5, 2);
$n= sizeof($arr);
printLeaders($arr, $n);
// This code is contributed
// by Shivi_Aggarwal
?>
Output:
2 5 17
Time Complexity: O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments