NEXTGREATER

Given an array, find the next greater element G[i] for every element A[i] in the array. The Next greater Element for an element A[i] is the first greater element on the right side of A[i] in array.
More formally,

G[i] for an element A[i] = an element A[j] such that 
    j is minimum possible AND 
    j > i AND
    A[j] > A[i]

Elements for which no greater element exist, consider next greater element as -1.

Input : A : [4, 5, 2, 10]
Output : [5, 10, 10, -1]

Input : A : [3, 2, 1]
Output : [-1, -1, -1]

Method:

Traverse the array from back, use a stack to keep track of elements that are greater than current element.

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public ArrayList<Integer> nextGreater(ArrayList<Integer> A) {
        Deque<Integer> stack = new ArrayDeque<>();
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = A.size() - 1; i >= 0; i --) {
            int val = A.get(i);
            while (!stack.isEmpty() && stack.peekFirst() <= val) {
                stack.pollFirst();
            }
            if (stack.isEmpty()) {
                result.add(-1);
            } else {
                result.add(stack.peekFirst());
            }
            stack.push(val);
        }
        Collections.reverse(result);
        return result;
    }
}