Posted on by Kalkicode
Code Array

# Find leaders in an array

Finding leaders in an array is a common problem in programming. A leader in an array is an element that is greater than all the elements to its right in the array.

## Problem Statement

Given an array of integers, find all the leaders in the array. A leader is an element that is greater than all the elements to its right.

## Example

Consider the following array:

``arr = [3, 5, 8, 7, 3, 6, 2, 1, 4]``

The leaders in this array are `8`, `7`, `6`, and `4` because they are greater than all the elements to their right.

## Idea to Solve

To find the leaders in the array, iterate through the array from right to left. Keep track of the maximum element encountered so far. If the current element is greater than the maximum encountered element, it is a leader.

## Pseudocode

``````function find_leaders(arr, size):
max_right = arr[size - 1]
print(max_right)
for i from size - 2 to 0:
if arr[i] > max_right:
max_right = arr[i]
print(max_right)

// Example usage
arr = [3, 5, 8, 7, 3, 6, 2, 1, 4]
size = size(arr)
find_leaders(arr, size)``````

## Algorithm Explanation

1. The `find_leaders` function takes the array and its size as parameters.
2. It initializes `max_right` with the last element of the array since it is always a leader.
3. The function starts iterating through the array from the second-to-last element to the first element.
4. For each element, if it is greater than `max_right`, it updates `max_right` with the current element and prints it. This means the current element is a leader.

## Code Solution

``````/*
C program
Find leaders in an array
*/
#include <stdio.h>

//Display array element
void display(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("  %d", arr[i]);
}
printf("\n");
}
// Find all leader elements in given array
void findLeaders(int arr[], int size)
{
if (size <= 0)
{
return;
}
// Display array elements
printf("\n Array elements : ");
display(arr, size);
// Loop controlling variables
int i = 0;
int j = 0;
// Outer loop
for (i = 0; i < size; ++i)
{
// start to next element
j = i + 1;
// Check if that [i] element is largest than or equal to other upcoming element
while (j < size && arr[i] >= arr[j])
{
j++;
}
if (j == size)
{
// When get a new result
printf(" %d", arr[i]);
}
}
printf("\n");
}
int main()
{
// Define array of integer elements
int arr1[] = {
3 , 5 , 8 , 7 , 3 , 6 , 2 , 1 , 4
};
int arr2[] = {
2 , 8 , 3 , 5 , 7 , 2 , 9 , 7 , 3 , 4
};
int size = sizeof(arr1) / sizeof(arr1[0]);
//Test Case 1
findLeaders(arr1, size);
size = sizeof(arr2) / sizeof(arr2[0]);
//Test Case 2
findLeaders(arr2, size);
return 0;
}``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8 7 6 4

Array elements :   2  8  3  5  7  2  9  7  3  4
9 7 4``````
``````/*
Java Program
Find leaders in an array
*/
public class LeaderElement
{
//Display array element
public void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
System.out.print("  " + arr[i]);
}
System.out.print("\n");
}
// Find all leader elements in given array
public void findLeaders(int[] arr, int size)
{
if (size <= 0)
{
return;
}
// Display array elements
System.out.print("\n Array elements : ");
display(arr, size);
// Loop controlling variables
int i = 0;
int j = 0;
// Outer loop
for (i = 0; i < size; ++i)
{
// start to next element
j = i + 1;
// Check if that [i] element is largest than or equal to other upcoming element
while (j < size && arr[i] >= arr[j])
{
j++;
}
if (j == size)
{
// When get a new result
System.out.print("  " + arr[i]);
}
}
System.out.print("\n");
}
public static void main(String[] args)
{
LeaderElement obj = new LeaderElement();
// Define array of integer elements
int[] arr1 = {
3 , 5 , 8 , 7 , 3 , 6 , 2 , 1 , 4
};
int[] arr2 = {
2 , 8 , 3 , 5 , 7 , 2 , 9 , 7 , 3 , 4
};
int size = arr1.length;
//Test Case 1
obj.findLeaders(arr1, size);
size = arr2.length;
//Test Case 2
obj.findLeaders(arr2, size);
}
}``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4``````
``````// Include namespace system
using System;
/*
C# Program
Find leaders in an array
*/
public class LeaderElement
{
// Display array element
public void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write("  " + arr[i]);
}
Console.Write("\n");
}
//  Find all leader elements in given array
public void findLeaders(int[] arr, int size)
{
if (size <= 0)
{
return;
}
//  Display array elements
Console.Write("\n Array elements : ");
display(arr, size);
//  Loop controlling variables
int i = 0;
int j = 0;
//  Outer loop
for (i = 0; i < size; ++i)
{
//  start to next element
j = i + 1;
//  Check if that [i] element is largest than or equal to other upcoming element
while (j < size && arr[i] >= arr[j])
{
j++;
}
if (j == size)
{
//  When get a new result
Console.Write("  " + arr[i]);
}
}
Console.Write("\n");
}
public static void Main(String[] args)
{
LeaderElement obj = new LeaderElement();
//  Define array of integer elements
int[] arr1 = {
3 , 5 , 8 , 7 , 3 , 6 , 2 , 1 , 4
};
int[] arr2 = {
2 , 8 , 3 , 5 , 7 , 2 , 9 , 7 , 3 , 4
};
int size = arr1.Length;
// Test Case 1
obj.findLeaders(arr1, size);
size = arr2.Length;
// Test Case 2
obj.findLeaders(arr2, size);
}
}``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Find leaders in an array
*/

class LeaderElement
{
public:
// Display array element
void display(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << "  " << arr[i];
}
cout << "\n";
}
//  Find all leader elements in given array
void findLeaders(int arr[], int size)
{
if (size <= 0)
{
return;
}
//  Display array elements
cout << "\n Array elements : ";
this->display(arr, size);
//  Loop controlling variables
int i = 0;
int j = 0;
//  Outer loop
for (i = 0; i < size; ++i)
{
//  start to next element
j = i + 1;
//  Check if that [i] element is largest than or equal to other upcoming element
while (j < size && arr[i] >= arr[j])
{
j++;
}
if (j == size)
{
//  When get a new result
cout << "  " << arr[i];
}
}
cout << "\n";
}
};
int main()
{
LeaderElement obj = LeaderElement();
//  Define array of integer elements
int arr1[] = {
3 , 5 , 8 , 7 , 3 , 6 , 2 , 1 , 4
};
int arr2[] = {
2 , 8 , 3 , 5 , 7 , 2 , 9 , 7 , 3 , 4
};
int size = sizeof(arr1) / sizeof(arr1[0]);
// Test Case 1
obj.findLeaders(arr1, size);
size = sizeof(arr2) / sizeof(arr2[0]);
// Test Case 2
obj.findLeaders(arr2, size);
return 0;
}``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4``````
``````<?php
/*
Php Program
Find leaders in an array
*/
class LeaderElement
{
// Display array element
public	function display( \$arr, \$size)
{
for (\$i = 0; \$i < \$size; \$i++)
{
echo "  ". \$arr[\$i];
}
echo "\n";
}
//  Find all leader elements in given array
public	function findLeaders( \$arr, \$size)
{
if (\$size <= 0)
{
return;
}
//  Display array elements
echo "\n Array elements : ";
\$this->display(\$arr, \$size);
//  Loop controlling variables
\$i = 0;
\$j = 0;
//  Outer loop
for (\$i = 0; \$i < \$size; ++\$i)
{
//  start to next element
\$j = \$i + 1;
//  Check if that [i] element is largest than or equal to other upcoming element
while (\$j < \$size && \$arr[\$i] >= \$arr[\$j])
{
\$j++;
}
if (\$j == \$size)
{
//  When get a new result
echo "  ". \$arr[\$i];
}
}
echo "\n";
}
}

function main()
{
\$obj = new LeaderElement();
//  Define array of integer elements
\$arr1 = array(3, 5, 8, 7, 3, 6, 2, 1, 4);
\$arr2 = array(2, 8, 3, 5, 7, 2, 9, 7, 3, 4);
\$size = count(\$arr1);
// Test Case 1
\$obj->findLeaders(\$arr1, \$size);
\$size = count(\$arr2);
// Test Case 2
\$obj->findLeaders(\$arr2, \$size);
}
main();``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4``````
``````/*
Node Js Program
Find leaders in an array
*/
class LeaderElement
{
// Display array element
display(arr, size)
{
for (var i = 0; i < size; i++)
{
process.stdout.write("  " + arr[i]);
}
process.stdout.write("\n");
}
//  Find all leader elements in given array
findLeaders(arr, size)
{
if (size <= 0)
{
return;
}
//  Display array elements
process.stdout.write("\n Array elements : ");
this.display(arr, size);
//  Loop controlling variables
var i = 0;
var j = 0;
//  Outer loop
for (i = 0; i < size; ++i)
{
//  start to next element
j = i + 1;
//  Check if that [i] element is largest than or equal to other upcoming element
while (j < size && arr[i] >= arr[j])
{
j++;
}
if (j == size)
{
//  When get a new result
process.stdout.write("  " + arr[i]);
}
}
process.stdout.write("\n");
}
}

function main()
{
var obj = new LeaderElement();
//  Define array of integer elements
var arr1 = [3, 5, 8, 7, 3, 6, 2, 1, 4];
var arr2 = [2, 8, 3, 5, 7, 2, 9, 7, 3, 4];
var size = arr1.length;
// Test Case 1
obj.findLeaders(arr1, size);
size = arr2.length;
// Test Case 2
obj.findLeaders(arr2, size);
}
main();``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4``````
``````#  Python 3 Program
#  Find leaders in an array

class LeaderElement :
#  Display array element
def display(self, arr, size) :
i = 0
while (i < size) :
print("  ", arr[i], end = "")
i += 1

print(end = "\n")

#   Find all leader elements in given array
def findLeaders(self, arr, size) :
if (size <= 0) :
return

#   Display array elements
print("\n Array elements : ", end = "")
self.display(arr, size)
#   Loop controlling variables
i = 0
j = 0
#   Outer loop
while (i < size) :
#   start to next element
j = i + 1
#   Check if that [i] element is largest than or equal to other upcoming element
while (j < size and arr[i] >= arr[j]) :
j += 1

if (j == size) :
#   When get a new result
print("  ", arr[i], end = "")

i += 1

print(end = "\n")

def main() :
obj = LeaderElement()
#   Define array of integer elements
arr1 = [3, 5, 8, 7, 3, 6, 2, 1, 4]
arr2 = [2, 8, 3, 5, 7, 2, 9, 7, 3, 4]
size = len(arr1)
#  Test Case 1
obj.findLeaders(arr1, size)
size = len(arr2)
#  Test Case 2
obj.findLeaders(arr2, size)

if __name__ == "__main__": main()``````

#### Output

`````` Array elements :    3   5   8   7   3   6   2   1   4
8   7   6   4

Array elements :    2   8   3   5   7   2   9   7   3   4
9   7   4``````
``````#   Ruby Program
#   Find leaders in an array

class LeaderElement
#  Display array element
def display(arr, size)
i = 0
while (i < size)
print("  ", arr[i])
i += 1
end

print("\n")
end

#   Find all leader elements in given array
def findLeaders(arr, size)
if (size <= 0)
return
end

#   Display array elements
print("\n Array elements : ")
self.display(arr, size)
#   Loop controlling variables
i = 0
j = 0
#   Outer loop
while (i < size)
#   start to next element
j = i + 1
#   Check if that [i] element is largest than or equal to other upcoming element
while (j < size && arr[i] >= arr[j])
j += 1
end

if (j == size)
#   When get a new result
print("  ", arr[i])
end

i += 1
end

print("\n")
end

end

def main()
obj = LeaderElement.new()
#   Define array of integer elements
arr1 = [3, 5, 8, 7, 3, 6, 2, 1, 4]
arr2 = [2, 8, 3, 5, 7, 2, 9, 7, 3, 4]
size = arr1.length
#  Test Case 1
obj.findLeaders(arr1, size)
size = arr2.length
#  Test Case 2
obj.findLeaders(arr2, size)
end

main()``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4
``````
``````/*
Scala Program
Find leaders in an array
*/
class LeaderElement
{
//  Display array element
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + arr(i));
i += 1;
}
print("\n");
}
//   Find all leader elements in given array
def findLeaders(arr: Array[Int], size: Int): Unit = {
if (size <= 0)
{
return;
}
//   Display array elements
print("\n Array elements : ");
this.display(arr, size);
//   Loop controlling variables
var i: Int = 0;
var j: Int = 0;
//   Outer loop
while (i < size)
{
//   start to next element
j = i + 1;
//   Check if that [i] element is largest than or equal to other upcoming element
while (j < size && arr(i) >= arr(j))
{
j += 1;
}
if (j == size)
{
//   When get a new result
print("  " + arr(i));
}
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: LeaderElement = new LeaderElement();
//   Define array of integer elements
var arr1: Array[Int] = Array(3, 5, 8, 7, 3, 6, 2, 1, 4);
var arr2: Array[Int] = Array(2, 8, 3, 5, 7, 2, 9, 7, 3, 4);
var size: Int = arr1.length;
//  Test Case 1
obj.findLeaders(arr1, size);
size = arr2.length;
//  Test Case 2
obj.findLeaders(arr2, size);
}
}``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4``````
``````/*
Swift 4 Program
Find leaders in an array
*/
class LeaderElement
{
//  Display array element
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
//   Find all leader elements in given array
func findLeaders(_ arr: [Int], _ size: Int)
{
if (size <= 0)
{
return;
}
//   Display array elements
print("\n Array elements : ", terminator: "");
self.display(arr, size);
//   Loop controlling variables
var i: Int = 0;
var j: Int = 0;
//   Outer loop
while (i < size)
{
//   start to next element
j = i + 1;
//   Check if that [i]element is largest than or equal to other upcoming element
while (j < size && arr[i] >= arr[j])
{
j += 1;
}
if (j == size)
{
//   When get a new result
print("  ", arr[i], terminator: "");
}
i += 1;
}
print(terminator: "\n");
}
}
func main()
{
let obj: LeaderElement = LeaderElement();
//   Define array of integer elements
let arr1: [Int] = [3, 5, 8, 7, 3, 6, 2, 1, 4];
let arr2: [Int] = [2, 8, 3, 5, 7, 2, 9, 7, 3, 4];
var size: Int = arr1.count;
//  Test Case 1
obj.findLeaders(arr1, size);
size = arr2.count;
//  Test Case 2
obj.findLeaders(arr2, size);
}
main();``````

#### Output

`````` Array elements :    3   5   8   7   3   6   2   1   4
8   7   6   4

Array elements :    2   8   3   5   7   2   9   7   3   4
9   7   4``````
``````/*
Kotlin Program
Find leaders in an array
*/
class LeaderElement
{
//  Display array element
fun display(arr: Array<Int>, size: Int): Unit
{
var i: Int = 0;
while (i<size)
{
print("  " + arr[i]);
i += 1;
}
print("\n");
}
//   Find all leader elements in given array
fun findLeaders(arr: Array<Int>, size: Int): Unit
{
if (size <= 0)
{
return;
}
//   Display array elements
print("\n Array elements : ");
this.display(arr, size);
//   Loop controlling variables
var i: Int = 0;
var j: Int;
//   Outer loop
while (i<size)
{
//   start to next element
j = i + 1;
//   Check if that [i] element is largest than or equal to other upcoming element
while (j<size && arr[i] >= arr[j])
{
j += 1;
}
if (j == size)
{
//   When get a new result
print("  " + arr[i]);
}
i += 1;
}
print("\n");
}
}
fun main(args: Array<String>): Unit
{
var obj: LeaderElement = LeaderElement();
//   Define array of integer elements
var arr1: Array<Int> = arrayOf(3, 5, 8, 7, 3, 6, 2, 1, 4);
var arr2: Array<Int> = arrayOf(2, 8, 3, 5, 7, 2, 9, 7, 3, 4);
var size: Int = arr1.count();
//  Test Case 1
obj.findLeaders(arr1, size);
size = arr2.count();
//  Test Case 2
obj.findLeaders(arr2, size);
}``````

#### Output

`````` Array elements :   3  5  8  7  3  6  2  1  4
8  7  6  4

Array elements :   2  8  3  5  7  2  9  7  3  4
9  7  4``````

## Time Complexity

The algorithm iterates through the array once, from right to left, and performs constant-time operations. Therefore, the time complexity of the algorithm is `O(n)`, where `n` is the size of the array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post