Find Next greater element

Given an array, print the Next Greater Element for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements, for which no greater element exists, return -1.

For example for the array {3, 5, 19, 5, 1, 100, 90}

Next greater element for 3 is 5

Next greater element for 5 is 19

Next greater element for 19 is 100

Next greater element for 5 is 100

Next greater element for 1 is 100

Next greater element for 100 is -1

Next greater element for 90 is -1

Algorithm is simple

Traverse array from last to first.

Step 1: Add last element to stack. Greater element for last element is -1.

Step 2: Traverse array from last-1 to first. Pop all elements that are <= to this element from stack. If stack is empty, greater element for this element is -1, else top element of the stack is greater element. Add current element to stack.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;

public class ArrayUtil {

 public static int[] printNextGreaterElements(int arr[]) {
  Objects.nonNull(arr);
  int result[] = new int[arr.length];
  int length = arr.length - 1;

  result[length] = -1;
  LinkedList<Integer> list = new LinkedList<>();
  list.push(arr[length]);

  for (int i = length - 1; i > -1; i--) {
   while (list.peek() != null && arr[i] >= list.peek()) {
    list.pop();
   }

   if (list.peek() == null) {
    result[i] = -1;
   } else {
    result[i] = list.peek();
   }
   list.push(arr[i]);
  }

  return result;
 }

 public static void main(String args[]) {
  int arr1[] = { 3, 5, 19, 5, 1, 100, 90 };
  int arr2[] = { 4, 5, 2, 25 };
  int arr3[] = { 13, 7, 6, 12 };
  int arr4[] = { 7, 4, 5, 5, 9, 2, 5, 2, 5, 7 };
  int arr5[] = { 9, 7, 8, 10 };
  int arr6[] = { 34, 35, 27, 42, 5, 28, 39, 20, 28 };
  int arr7[] = { 1, 1, 1, 1 };
  int arr8[] = { 4, 7, 5 };
  int arr9[] = { 5, 7, 2, 4, 8, 6 };

  System.out.println("For arr1 : "
    + Arrays.toString(printNextGreaterElements(arr1)));
  System.out.println("For arr2 : "
    + Arrays.toString(printNextGreaterElements(arr2)));
  System.out.println("For arr3 : "
    + Arrays.toString(printNextGreaterElements(arr3)));
  System.out.println("For arr4 : "
    + Arrays.toString(printNextGreaterElements(arr4)));
  System.out.println("For arr5 : "
    + Arrays.toString(printNextGreaterElements(arr5)));
  System.out.println("For arr6 : "
    + Arrays.toString(printNextGreaterElements(arr6)));
  System.out.println("For arr7 : "
    + Arrays.toString(printNextGreaterElements(arr7)));
  System.out.println("For arr8 : "
    + Arrays.toString(printNextGreaterElements(arr8)));
  System.out.println("For arr9 : "
    + Arrays.toString(printNextGreaterElements(arr9)));
 }
}

Output

For arr1 : [5, 19, 100, 100, 100, -1, -1]
For arr2 : [5, 25, 25, -1]
For arr3 : [-1, 12, 12, -1]
For arr4 : [9, 5, 9, 9, -1, 5, 7, 5, 7, -1]
For arr5 : [10, 8, 10, -1]
For arr6 : [35, 42, 42, -1, 28, 39, -1, 28, -1]
For arr7 : [-1, -1, -1, -1]
For arr8 : [7, -1, -1]
For arr9 : [7, 8, 4, 8, -1, -1]