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