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.

New Comment