Find leader elements/numbers in integer array (java/example/iterative algorithm)

• Given an integer array in java, find out the leader elements in an array.
• What is leader element in an array?
  • The element which is greater than the elements to its right.
• The element on the extreme right, is assumed to be the leader element.

1. Examples: leader elements/ numbers in integer array (java/ example)

1.1 Example #1

• Given an integer array { 25, 10, 2, 4, 1, 3 } in java.
• Find out the elements, which are greater than the elements on its right
  • e.g 25 is greater than all elements on its right
  • Hence 25 is one of the leader element.
• Leaders in an array are : 25, 10, 4, 3

1.2 Example #2

• Given an integer array { 40, 50, 45, 47 } in java
• Find out the elements, which are greater than the elements on its right
  • e.g 50 is greater than all elements on its right
  • Hence 50 is one of the leader element.
• Leaders in an array are : 50 47

2. Iterative algorithm – find leader elements/numbers in integer array (java)

1. Traverse the array from right to left in java.
2. We will use stack to print elements.
3. Create a variable maxElement to demonstrate the maximum element.
4. Initialize maxElement = right most element.
5. The rightmost element is leader element.
   • push right most element to stack.
6. Traverse input array from right to left
   • Note down the current element of iteration.
   • If current element is greater than maxElement.
     • Update the maxElement by current element.
     • push the leader element on to the stack.
7. end of array traversal
8. Print all leader elements present in a stack.

Time complexity of algorithm is O (n).

3. Program – find leader elements/numbers in integer array (java/example)

package org.learn.arrays;

import java.util.Arrays;
import java.util.Stack;

public class LeadersInArray {

	public static void main(String[] args) {

		int[] arr = { 25, 10, 2, 4, 1, 3 };
		System.out.printf("1. Input array is : %s", Arrays.toString(arr));
		printLeaders(arr);
		
		arr = new int[] { 40, 50, 45, 47 };
		System.out.printf("\n2. Input array is : %s", Arrays.toString(arr));
		printLeaders(arr);
	}

	private static void printLeaders(int[] arr) {
		Stack<Integer> stack = new Stack<Integer>();
		int lastIndex = arr.length - 1;
		
		int maxElement = arr[lastIndex];
		arr[lastIndex--] = -1;
		stack.push(maxElement);

		while (lastIndex >= 0) {

			int current = arr[lastIndex];
			if (current > maxElement) {
				maxElement = current;
				stack.push(maxElement);
			}
			lastIndex--;
		}

		System.out.printf("\nLeaders in an array : ");
		while (!stack.isEmpty()) {
			System.out.printf("%d ", stack.pop());
		}
	}
}

4. Output – print leader elements/numbers in integer array (java/example)

1. Input array is : [25, 10, 2, 4, 1, 3]
Leaders in an array : 25 10 4 3 
2. Input array is : [40, 50, 45, 47]
Leaders in an array : 50 47