Find next higher element in an array for each element [closed]

Question

From a given input array, for each element, find next higher element present in each array. For example {40,50,11,32,55,68,75} output should be {50,55,32,55,68,75,-1}. For element if no higher element is present, print -1.

Complexity should be less than O(n^2). You can use data structures and no constraint on space complexity.

Answer 1

You can use a Stack and the time complexity is O(N).

The algorithm:
Start from the left side and move towards the right. When you pick an element from the array (let's say x), pop the Stack until the elements from the Stack (lets say y) has an element greater than the array element i.e. x> y. Then push the element i.e. x to stack.

e.g. {40,50,11,32,55,68,75} . here s is stack.

40, as s is empty push it. s: 40

50, as s.peek() < 50 so pop 40 (40's greater element is 50) then push 50. s: 50

Next higher element of 40 - 50.

11, s.peek() > 11 so push 11. s: 50, 11

32, s.peek() < 32, so pop the element and now it's 50 which is greater than 32 hence push 32. s: 50 ,32

Next higher element of 11 - 32.

55, s.peek() < 55, so pop the element i.e. 32 then pop next as well as 50 < 55, then push 55. s: 55.

Next higher element of 32 - 55.

Next higher element of 50 - 55.

68, s.peek() < 68 so pop it and push 68. s: 68

75, s.peek() < 75 so pop it and push 75 s:75.

Next higher element of 68 - 75.

As the array does not have any element no just pop the stack say that for all the elements inside the array does not have greater element i.e. -1.

Next higher element of 75 - -1.

The same algorithm in code:

public static void getNGE(int[] a) {
    Stack<Integer> s = new Stack<Integer>();
    s.push(a[0]);

    for (int i = 1; i < a.length; i++) {
        if (s.peek() != null) {
            while (true) {
                if (s.peek() == null || s.peek() > a[i]) {
                    break;
                }
                System.out.println(s.pop() + ":" + a[i]);
            }
        }
        s.push(a[i]);
    }
    while (s.peek() != null) {
        System.out.println(s.pop() + ":" + -1);
    }
}

Answer 2

A key property of your question, seen in the output 55 for input 32, is that you apparently only want those larger elements which come after a given input element in the input sequence. Otherwise the output at that point would have been 40.

I suggest you process the array from the right, and maintain a tree (e.g. a red-black tree) of seen elements. For every element you process, you first seach the tree in O(log n) for the next larger element. You store that in O(1) for the result you want to print at the end, then insert the currently processed element into the tree in O(log n). Processing all elements in this fashion in O(n log n), then reverse the list of things you have to output in O(n) and you are done.