Optimized solution in Java O(n)


#1

public class Solution {
public ArrayList nextGreater(ArrayList A) {

    ArrayList<Integer> output = new ArrayList<Integer>();
    
    if(A.size() == 0)
        return output;
    
    if(A.size() == 1){
        output.add(-1);
        return output;
    }
    
    Integer [] arr = new Integer[A.size()];
	output = new ArrayList<>(Arrays.asList(arr));
	Collections.fill(output, 0);
    Stack<Integer> stack = new Stack<Integer>();
    
    for (int i=0; i<A.size(); i++) {
        while (!stack.isEmpty() && A.get(stack.peek()) < A.get(i))
        {
            int index = stack.pop();
            output.set(index, A.get(i));
        }
        stack.push(i);
    }   
    while (!stack.isEmpty()) {
        int index = stack.pop();
        output.set(index, -1);
    }
    return output;
}

}