What is the real intuition behind using stack in finding Next Greater Element in Array

Question

I was asked of a question in my interview which was returning ans array in which, ans[i] = next greater element of A[i] and if element don't have next greater put -1 there.

Example: 
A = [1, 2, 1, 3, 4]
ans = [2, 3, 3, 4, -1]   

I was not able to give optimized approach, but I searched on internet and found it will we done using a stack, but everywhere I just found the algo of solving the question not the reason/intuition that why this works, after reading also I also agree yes that will work fine but how will someone who never did this question will think towards of using a stack.

If anyone could help me out it will be a great help! :)

Answer 1

You could imagine the input as representing bars in a vertical bar chart. For example:

       

The arrows indicate a sort of "influence" that higher bars have to their left side. You could imagine someone standing at the top of the bar and looking towards the left. Or you could think of water that fills up between those bars, and when it reaches the height of the current bar, you know their field of influence. Their influence stops where a bar is encountered that has at least their own height, or when the left side of the chart is encountered.

It makes sense that higher bars typically have a longer stretch of influence.

Now when we iterate the bars from left to right we can see how this can be used to produce the output. The 7 has influence over the 2, so 7 is added to the output at index 0 (the index of value 2).

The next value of interest, is 4. It has influence over two preceding values, so at their indices (i.e. at index 3 and 4) we should output 4.

The next value of interest, is 6. It has influence over more values, of which only the 5 at index 2 is "new". So at index 2 we should output 6.

We note that for an output at index 1 (to cover for value 7) we need to continue the process until reaching value 8. Some outputs can be determined in the mean time, while the 7 should "wait" for its next greater value to be found.

This should give you a feel of using a stack. The assignment to index 4, 3, 2, 1 happened in backwards order, much like you get when popping those indices from a stack. Before index 1 would be popped, some indices would be pushed to the stack and popped again, but finally 7 can be popped too, ending its longer wait.

This popping also ensures that an output index will only be assigned a value once.

I realise you don't need to see the algorithm itself, as you already know it. Hopefully this helped clarify a bit what the intuition is behind it.

Answer 2

In an increasing section of A, the next greater element is just the next. And when there is a decrease, you have to wait until you reach a larger value.

E.g.

1, 2, 1, 3, 4

can be seen as two increasing sections

1, 2||1, 3, 4

giving the next greater elements

2, -||3, 4, -

When you reach the 2 (in the original array), you have to wait until you reach 3 (in the original array) and conclude

2, 3, 3, 4, -

When you reach the 4 (in the original array), you have to wait... forever as there is no greater element.

---

Now the need for a stack stems from the fact that if you progress from left to right, there can be several waiting elements. As these elements form a decreasing section, they will be "served" smallest first, which correspond to LIFO order.